tag:blogger.com,1999:blog-83830042329318992162024-03-13T10:52:59.591-04:00Designing ParaSail, a new programming languageThis 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.Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.comBlogger120125tag:blogger.com,1999:blog-8383004232931899216.post-49683843206370422622020-07-10T22:35:00.004-04:002020-07-10T22:36:26.399-04:00A new blog on the Design and Engineering of Programming Languages<div>I am happy to announce a new blog about the Design and Engineering of Programming Languages. Only two entries so far. Here is the first:</div><div><span><span class="w4txWc oJeWuf" id="c306" role="region"><span class="MUhG4e OGjyyf" data-blogurl="http://designandengineerpl.blogspot.com/"><br /></span></span></span></div><div><span><span class="w4txWc oJeWuf" id="c306" role="region"><span class="MUhG4e OGjyyf" data-blogurl="http://designandengineerpl.blogspot.com/"> <a href="http://designandengineerpl.blogspot.com/2020/07/the-role-of-programming-languages.html">http://designandengineerpl.blogspot.com/2020/07/the-role-of-programming-languages.html</a></span></span></span></div><div><span><span class="w4txWc oJeWuf" id="c306" role="region"><span class="MUhG4e OGjyyf" data-blogurl="http://designandengineerpl.blogspot.com/"><br /></span></span></span></div><div><span><span class="w4txWc oJeWuf" id="c306" role="region"><span class="MUhG4e OGjyyf" data-blogurl="http://designandengineerpl.blogspot.com/">The intent is ultimately to create a book-length series of writings on the topic. Of course, we know where good intentions can lead! In any case, we hope these blog entries will at least make some interesting reading, even if together they never quite reach book length.</span></span></span></div><div><span><span class="w4txWc oJeWuf" id="c306" role="region"><span class="MUhG4e OGjyyf" data-blogurl="http://designandengineerpl.blogspot.com/"><br /></span></span></span></div><div><span><span class="w4txWc oJeWuf" id="c306" role="region"><span class="MUhG4e OGjyyf" data-blogurl="http://designandengineerpl.blogspot.com/">My day job went down to 60% as of July 1st, 2020, so my plan is to find more time to work on ParaSail, its various siblings such as Parython and Javallel, this new blog/book, and a new language on the drawing board, "ParaDISO" (Parallel Distributed, Incremental, Streamable Objects), for distributed/cloud computing. So now you know what is my definition of fun...<br /></span></span></span></div>Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-81849448671091636522019-10-31T18:09:00.000-04:002019-11-02T22:21:28.779-04:00Release 8.4 of ParaSail Interpreter, Compiler, and Debugger<div dir="ltr" style="text-align: left;" trbidi="on">
<div>
<div style="overflow: auto;">
<div style="max-height: 10000px;">
<div dir="ltr">
<div>
We
are happy to announce a new release of ParaSail. This new release
incorporates an enhanced interactive debugger that is automatically
invoked when
the interpreter encounters an assertion, precondition, or postcondition
that fails at run-time. In addition, the sources for run-time library
code that is potentially linked into compiled ParaSail programs now
carries a license which allows such compiled programs to be distributed
as the user sees fit.</div>
<br />
<div>
In any case, here is the new release [link updated -- was incorrect]:</div>
<div>
<br /></div>
<div>
<a href="http://bit.ly/psl84rel" rel="nofollow" target="_blank">http://bit.ly/psl84rel</a></div>
<div>
<br /></div>
<div>
It
is a "zip" archive of sources and binaries for Mac, Linux, and
Windows. Mac and Linux include executable binaries for a bootstrapped
LLVM-generating ParaSail compiler. Windows only contains the executable
binaries for the ParaSail interpreter.</div>
<div>
<br /></div>
<div>
The web page for ParaSail is still:</div>
<div>
<br /></div>
<div>
<a href="http://parasail-lang.org/" rel="nofollow" target="_blank">http://parasail-lang.org</a></div>
<div>
<br /></div>
<div>
From
a documentation point of view, the most exciting news is that we have
recently published a full description of the ParaSail language in the
new
academic "Programming Journal":</div>
<div>
<br /></div>
<div>
<a href="http://programming-journal.org/2019/3/7/" rel="nofollow" target="_blank">http://programming-journal.<wbr></wbr>org/2019/3/7/</a></div>
<div>
<br /></div>
<div>
Please
take a look at this article to see a comprehensive description of
ParaSail, and how it fits into the world of programming language design.</div>
<div>
<br /></div>
<div>
Here
is the latest reference manual (which is also linked from the ParaSail
web page, and included in the "zip" archive for release 8.4):</div>
<div>
<br /></div>
<div>
<a href="https://adacore.github.io/ParaSail/images/parasail_ref_manual.pdf" rel="nofollow" target="_blank">https://adacore.github.io/<wbr></wbr>ParaSail/images/parasail_ref_<wbr></wbr>manual.pdf</a></div>
<div>
<br /></div>
Enjoy!</div>
</div>
</div>
</div>
</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-60052328085450907282019-02-10T10:34:00.000-05:002019-02-10T10:35:26.162-05:00ParaSail Published in Programming Journal Vol. 3, Issue 3<div dir="ltr" style="text-align: left;" trbidi="on">
We very recently had a long paper on <b>ParaSail</b> published in the relatively new <i>Journal of the Art, Science, and Engineering of Programming</i> (<a href="http://programming-journal.org/">http://programming-journal.org</a>). This is an interesting journal, which is trying to rejuvenate the writing of Computer Science <i>journal</i> articles, rather than having essentially all interesting research showing up as Computer Science conference papers. Conference papers often tend to be <i>incremental,</i> being a report on recent progress in CS research activities, but not necessarily having the space or time to provide an <i>archival</i>-level quality and depth that might be possible in a journal article. In any case, here is the abstract for the ParaSail paper:<br />
<br />
<a href="http://programming-journal.org/2019/3/7/">http://programming-journal.org/2019/3/7/</a><br />
<br />
and from there you can click through to the full PDF (the <programming> journal is all <i>open access</i>). Many thanks to the editors and reviewers for their guidance in bringing this paper up to journalistic standards. </programming><br />
<br />
In fact, the <programming> journal has kind of flipped things around. If a paper is accepted for publication in the journal in a given year, they invite the author(s) to present the paper at their annual conference, which this year is in Genoa, Italy, the first week in April:</programming><br />
<br />
<a href="https://2019.programming-conference.org/">https://2019.programming-conference.org/</a><br />
<br />
So come on down to Genoa in April if you are in the neighborhood. The presentation on ParaSail will be on Thursday, April 4th.</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-65262624287300850652019-02-10T10:20:00.001-05:002019-02-10T10:20:11.653-05:00String interpolation comes to ParaSail 8.0<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="font-family: inherit;"><b>ParaSail</b> supports <i>generic</i> functions where the type of the parameter is determined at the point of call. The most common use of this capability is with the string concatenation operator "|":</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"> interface PSL::Core::Univ_String<> is</span><br />
<span style="font-family: inherit;"> ...</span><br />
<span style="font-family: inherit;"> op "|"(Left, Right : optional Univ_String) -> Univ_String<br /> is import(#concat_string)<br /><br /> op "|"(Left : optional Univ_String;<br /> Right : optional Right_Type is Imageable<>)<br /> -> Univ_String<br /><br /> op "|"(Left : optional Left_Type is Imageable<>;<br /> Right : optional Univ_String)<br /> -> Univ_String</span><br />
<span style="font-family: inherit;"> ...</span><br />
<span style="font-family: inherit;"> end interface PSL::Core::Univ_String</span><br />
<br />
<br />
<br />
<span style="font-family: inherit;">The first "|" provides the builtin string concatenation. The other two are generic functions defined in terms of this builtin concatenation, as follows:</span><br />
<br />
<br />
<span style="font-family: inherit;"> class PSL::Core::Univ_String is</span><br />
<span style="font-family: inherit;"> ...</span><br />
<span style="font-family: inherit;"> exports</span><br />
<span style="font-family: inherit;"> ...</span><br />
<span style="font-family: inherit;"> op "|"(Left : optional Univ_String;<br /> Right : optional Right_Type is Imageable<>)<br /> -> Univ_String is<br /> if Right is null then<br /> return Left | "null"<br /> else<br /> return Left | Right_Type::To_String(Right)<br /> end if<br /> end op "|"<br /><br /> op "|"(Left : optional Left_Type is Imageable<>;<br /> Right : optional Univ_String)<br /> -> Univ_String is<br /> if Left is null then<br /> return "null" | Right<br /> else<br /> return Left_Type::To_String(Left) | Right<br /> end if<br /> end op "|"<br /> ...</span><br />
<span style="font-family: inherit;"> end class PSL::Core::Univ_String</span><br />
<br />
<span style="font-family: inherit;"><br />---</span><br />
<br />
<span style="font-family: inherit;">What the above means is that when you write:</span><br />
<br />
<span style="font-family: inherit;"> "X = " | X</span><br />
<br />
<span style="font-family: inherit;">this will be allowed so long as "X" is of a type that satisfies the "Imageable" interface, which is defined as follows:</span><br />
<br />
<span style="font-family: inherit;"> abstract interface PSL::Core::Imageable<> is<br /> func To_String(Val : Imageable) -> Univ_String<><br /><br /> optional func From_String(Str : Univ_String<>) -> optional Imageable<br /><br /> // NOTE: We include Hashable<> operations here<br /> // so that Set<imageable> works nicely.<br /> // Clearly if something is Imageable it is possible<br /> // to implement "=?" and Hash using the string image,<br /> // so we might as well requires these operations too.<br /><br /> op "=?"(Left, Right : Imageable) -> Ordering<br /> func Hash(Val : Imageable) -> Univ_Integer<br /> end interface PSL::Core::Imageable<br /> </imageable></span><br />
<span style="font-family: inherit;">---</span><br />
<span style="font-family: inherit;">The availability of the To_String operation is the critical aspect of Imageable that we use for the "|" operator. We expand "X = " | X into:</span><br />
<br />
<span style="font-family: inherit;"> "X = " | To_String(X)</span><br />
<br />
<span style="font-family: inherit;">and so long as X's type has an appropriate To_String operation, everything works smoothly. What this means is that you almost never have to write a call on To_String explicitly, by just alternating between string literals and expressions that you want to print, you can write things like:</span><br />
<br />
<span style="font-family: inherit;"> Println ("X = " | X | ", Y = " | Y | ", X + Y = " | X + Y | "!");</span><br />
<br />
<span style="font-family: inherit;">which is clearly less verbose than:</span><br />
<br />
<span style="font-family: inherit;"> Println ("X = " | To_String(X) | ", Y = " | To_String(Y) | ", X + Y = " | To_String(X + Y) | "!");</span><br />
<br />
<span style="font-family: inherit;">Nevertheless, even in the more concise version, all of those alternating quotes and '|' characters can become hard for the human to parse, and it is easy to forget one of the needed characters. So what to do?</span><br />
<br />
<span style="font-family: inherit;"><b>STRING INTERPOLATION</b> </span><br />
<br />
<span style="font-family: inherit;"></span><span style="font-family: inherit;">A (growing) number of languages support the ability to "interpolate" the values of variables, or in some cases expressions, directly into string literals. This has been true for simple variables since the beginning for languages like the Unix/GNU-Linux shell:</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"> echo "X = $X, Y = $Y"</span><br />
<br />
<span style="font-family: inherit;">Interpolating the value of more complex expressions is sometimes supported, but generally requires some additional syntax. </span><br />
<br />
<span style="font-family: inherit;">Very early on, most variants of the LISP language supported the ability to construct list structures explicitly, using the "quote" operation, along with an ability to insert a LISP expression (aka "S-expression") in the middle that was to be evaluated and substituted into the list structure that was being defined. E.g.:</span><br />
<br />
<span style="font-family: inherit;"> (define celebrate (lambda (name) (quote (Happy Birthday to (unquote (capitalize name))))))</span><br />
<br />
<span style="font-family: inherit;">and then "(celebrate (quote sam))" evaluates to "(Happy Birthday to Sam)".</span><br />
<br />
<span style="font-family: inherit;">As a short-hand, in most versions of LISP:</span><br />
<br />
<span style="font-family: inherit;"> (quote (a b c))</span><br />
<br />
<span style="font-family: inherit;">becomes something like:</span><br />
<br />
<span style="font-family: inherit;"> '(a b c)</span><br />
<br />
<span style="font-family: inherit;">and (unquote blah) becomes, depending on the version of LISP, something like:</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"> `blah</span><br />
<span style="font-family: inherit;">or</span><br />
<span style="font-family: inherit;"> ,blah</span><br />
<br />
<span style="font-family: inherit;">So the above definition of "celebrate" using these short-hands becomes:</span><br />
<br />
<span style="font-family: inherit;"> (define celebrate (lambda (name) '(Happy Birthday to ,(capitalize name))))</span><br />
<br />
<span style="font-family: inherit;">with (celebrate 'sam) becoming (Happy Birthday to Sam)</span><br />
<br />
<span style="font-family: inherit;"><b>PARASAIL STRING INTERPOLATION</b></span><br />
<br />
<span style="font-family: inherit;">Ok, so how does this relate to ParaSail? So the explicit use of the "|" operator and having to end a string literal, insert the expressions between | ... |, and then restart the string literal gets old. Given that there aren't an infinite number of ParaSail programs already in existence, and the fact that the back-quote character is almost never used, we decided to hi-jack the meaning of back-quote when it appears in the middle of a string literal to reduce all the back and forth needed when using an explicit "|" operator. Hence, we now allow:</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"> Println("X = `(X), Y = `(Y), X + Y = `(X + Y)!");</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">In other words, you can "interpolate" the value of an arbitrary (Imageable) expression into the middle of a ParaSail string literal by using `(<expr>). This is actually recognized during lexical analysis, and a mechanical expansion is performed by the lexical analyzer, of a back-quote character (unless preceded by '\') into the two characters: " |</expr></span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">The lexical analyzer then expects a left parenthesis to be the next character, and counts matching parentheses, and when it reaches the matching right parenthesis, it emits the two characters: | "</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">The net effect is that "X = `(X), ..." becomes:</span><br />
<br />
<span style="font-family: inherit;"> "X = " | (X) | ", ..."</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">Note that the parentheses are preserved, to avoid issues with precedence between the "|" operator and operators that might occur within the parentheses. Also note that the parenthesized expression can be separated from the back-quote by white space, and the expression can also span multiple lines if necessary. The lexer is smart enough to use a stack, so that the parenthesized expression can also have nested string literals, that themselves use interpolation.</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">If you have looked at past source releases of the ParaSail LLVM-based compiler (which is itself written in Parasail -- see lib/compiler.psl), you might want to take a look at the version of lib/compiler.psl in the 8.0 release. It makes heavy use of string interpolation, and hopefully is easier to read because of that.</span><br />
<span style="font-family: inherit;"> </span><br />
<br />
<span style="font-family: inherit;"> </span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"> </span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><br /></span></div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-51191113386463673492019-02-09T06:57:00.001-05:002019-02-09T06:57:47.915-05:00Release 8.0 of ParaSail Interpreter, Compiler, and Debugger<div dir="ltr" style="text-align: left;" trbidi="on">
<div>
Finally, at long last a new release of ParaSail. This new release
incorporates an interactive debugger that is automatically invoked when
the interpreter encounters an assertion, precondition, or postcondition
that fails at run-time. This is also the first release where pre- and
postconditions are fully analyzed, and checked at run-time. Finally,
this has one modest enhancement to the ParaSail syntax --
"interpolation" of the value of an expression directly into a string
literal. For example:</div>
<div>
<br /></div>
<div>
Println("The value of X + Y is `(X + Y).");</div>
<div>
<br /></div>
<div>
The
back-quote character followed by a parenthesized expression may now
appear within a string literal, and the value of the expression is
"interpolated" into the middle of the string, in place of the
back-quoted expression. Hence, presume X is 31 and Y is 11, the above
will print:</div>
<div>
<br /></div>
<div>
The value of X + Y is 42.</div>
<div>
<br /></div>
<div>
In any case, here is the new release:</div>
<div>
<br /></div>
<div>
<a href="http://bit.ly/psl8rel" rel="nofollow" target="_blank">http://bit.ly/psl8rel</a></div>
<div>
<br /></div>
<div>
It
is a "zip" archive of sources and binaries for Mac, Linux, and
Windows. Mac and Linux include executable binaries for a bootstrapped
LLVM-generating ParaSail compiler. Windows only contains the executable
binaries for the ParaSail interpreter.</div>
<div>
<br /></div>
<div>
The web page for ParaSail has also been updated:</div>
<div>
<br /></div>
<div>
<a href="http://parasail-lang.org/" rel="nofollow" target="_blank">http://parasail-lang.org</a></div>
<div>
<br /></div>
<div>
From
a documentation point of view, the most exciting news is that we have
just published a full description of the ParaSail language in the new
academic "Programming Journal":</div>
<div>
<br /></div>
<div>
<a href="http://programming-journal.org/2019/3/7/" rel="nofollow" target="_blank">http://programming-journal.<wbr></wbr>org/2019/3/7/</a></div>
<div>
<br /></div>
<div>
Please
take a look at this article to see a comprehensive description of
ParaSail, and how it fits into the world of programming language design.</div>
<div>
<br /></div>
<div>
Here
is the latest reference manual (which is also linked from the ParaSail
web page, and included in the "zip" archive for release 8.0):</div>
<div>
<br /></div>
<div>
<a href="https://adacore.github.io/ParaSail/images/parasail_ref_manual.pdf" rel="nofollow" target="_blank">https://adacore.github.io/<wbr></wbr>ParaSail/images/parasail_ref_<wbr></wbr>manual.pdf</a></div>
<div>
<br /></div>
We will be posting some follow-up blog entries about some of the new features in this release, in particular the debugger, and the implementation of postconditions that require automatically saving some values only available on entry to an operation.<br />
<br />
Enjoy!</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-3118735812971945412016-11-02T21:38:00.000-04:002016-11-03T08:29:03.773-04:00Release 7.0 of ParaSail interpreter, VM, and compiler -- sources plus linux/mac binaries<div dir="ltr" style="text-align: left;" trbidi="on">
We have just made a release of the ParaSail interpreter, VM,
llvm-based compiler, and ParaScope static analysis tool (aka "static
catcher of programming errors"). This is version 7.0. It includes a
nearly complete re-write of the llvm-based compiler. After attempting
other approaches, we finally went back to the ParaSail front end and had
it annotate every PSVM instruction with a set of virtual register
numbers in addition to a stack offset for local variables. This allows
the backend to generate much better LLVM (and eventually will also
simplify the job of doing more advanced static analysis). The compiler
also automatically inlines small routines, including routines from the
ParaSail standard library, so function call overhead in the presence of
layers of abstraction can be much reduced.<br />
<br />
This
release is the first in a while to include binaries, though it only
includes binaries for Mac and Linux (Windows is being difficult ...
;-{). The release is at:<br />
<br />
<a href="http://bit.ly/psl7rel" rel="" target="_blank">http://bit.ly/psl7rel</a><br />
<br />
If you have any problems, please report them on the ParaSail google group:<br />
<br />
<a href="https://groups.google.com/forum/#!forum/parasail-programming-language" target="_blank">https://groups.google.com/forum/#!forum/parasail-programming-language</a> </div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com4tag:blogger.com,1999:blog-8383004232931899216.post-68952121192421009452015-11-06T20:02:00.000-05:002015-11-06T20:02:06.968-05:00ParaSail source release 6.5 now available.<div dir="ltr" style="text-align: left;" trbidi="on">
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:<br />
<br />
http://bit.ly/ps6xsrc<br />
<br />
If you have any problems, please report them at:<br />
<br />
http://groups.google.com/group/parasail-programming-language</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-31801760357129564972015-01-05T18:20:00.000-05:002015-01-05T18:20:30.040-05:00Compiling ParaSail to LLVM, first in a series...<div dir="ltr" style="text-align: left;" trbidi="on">
We now have an LLVM-based compiler for <b>ParaSail</b>, 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 <a href="http://parasail-lang.org/">http://parasail-lang.org</a> <br />
<br />
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.<br />
<br />
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 <i>picothreads</i>, or parallel <i>work items</i> (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 <i>nested blocks</i> within a single PSVM <i>routine</i>. That is, a single ParaSail operation (<b>func</b> or <b>op</b>) produces a single PSVM routine, but that routine may have zero or more <i>nested blocks</i> 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.<br />
<br />
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 <i>Context</i>, the <i>Param_List</i>, and the <i>Static_Link</i>. The Param_List points to a <i>stack-based parameter list</i>, 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 <i>per-picothread</i> information. The Static_Link either points at a <i>type descriptor,</i> for a routine that corresponds to an operation of a module, or to the <i>enclosing stack frame</i>, 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 <i>up-level references</i> across multiple levels, as well as access to the type descriptor passed into an enclosing module operation.<br />
<br />
Type descriptors are fundamental to the ParaSail run-time model. Remember that at the source level, all ParaSail <i>modules</i> are considered <i>parameterized</i>, and a ParaSail <i>type</i> is produced by <i>instantiating</i> a module. Operations are generally associated with modules, and unlike in C++ or Ada, instantiating a module does <i>not</i> produce a new set of code for these operations. Instead, the code is generated <i>once</i> 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<i> type descriptor</i> provides -- all of the information that is dependent on the particular instantiation being used. <br />
<br />
For example, a Set module might have various operations like <span style="font-family: "Courier New",Courier,monospace;">Union</span> and <span style="font-family: "Courier New",Courier,monospace;">Intersection</span> and <span style="font-family: "Courier New",Courier,monospace;">Insert</span> and <span style="font-family: "Courier New",Courier,monospace;">Count</span>, 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 <i>Hashable</i>, which generally means <span style="font-family: "Courier New",Courier,monospace;">Hash</span> and "=?" (aka <i>compare</i>). So when we call the <span style="font-family: "Courier New",Courier,monospace;">Insert</span> 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++ <i>virtual function table</i>. 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 <span style="font-family: "Courier New",Courier,monospace;">Hash</span> 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 <span style="font-family: "Courier New",Courier,monospace;">Hash</span> and Integer "=?" routines, which will certainly be needed at least for the <span style="font-family: "Courier New",Courier,monospace;">Insert</span> routine.<br />
<br />
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 <span style="font-family: "Courier New",Courier,monospace;">Insert</span> routine know where it can find the <span style="font-family: "Courier New",Courier,monospace;">Hash</span> and "=?" routines for Integer or String, given that they might also have many other routines? The solution here is an <i>extra level of indirection</i>. We actually have two types of type descriptors, one is the <i>full</i> 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 <i>operation map </i>(or <i>op map</i> for short). This consists of a reference to the <i>full</i> 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.<br />
<br />
Note that this op-map approach does <i>not</i> work for languages where all objects carry around a reference to their type descriptor at run-time, since a <i>single</i> type descriptor must work for all uses of the object. One of the features of ParaSail is that typical objects have <i>no</i> 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 <i>polymorphic</i> 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 (<span style="font-family: "Courier New",Courier,monospace;">To_String</span>, <span style="font-family: "Courier New",Courier,monospace;">From_String</span>, <span style="font-family: "Courier New",Courier,monospace;">Hash</span>, 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.<br />
<br />
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 <i>always</i> a <i>full</i> type descriptor, and the compiled code can rely on that fact.</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com1tag:blogger.com,1999:blog-8383004232931899216.post-9727968518221313982015-01-04T13:45:00.002-05:002015-01-04T13:45:48.167-05:00Expanded paper on ParaSail pointer-free parallelism<div dir="ltr" style="text-align: left;" trbidi="on">
Here is a PDF for a recent paper describing in more depth <b>ParaSail</b>'s pointer-free approach to parallelism:<br />
<br />
<a href="http://bit.ly/ps15pfp">http://bit.ly/ps15pfp</a><br />
<br />
Here is the <b>abstract</b> from the paper:<br />
<span style="font-size: small;"><br /></span>
<br />
<div class="page" title="Page 1">
<span style="font-size: small;">
</span><div class="layoutArea">
<span style="font-size: small;">
</span><div class="column">
<span style="font-size: small;">
</span><span style="font-size: small;"><span style="font-family: "TimesNewRomanPSMT";">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 </span><span style="font-family: "TimesNewRomanPS"; font-style: italic;">expandable </span><span style="font-family: "TimesNewRomanPSMT";">(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. </span></span><br />
</div>
</div>
</div>
</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com1tag:blogger.com,1999:blog-8383004232931899216.post-20523562092576771422014-07-25T14:36:00.000-04:002014-07-25T14:36:14.356-04:00Progress Update<h4>
Bootstrapping</h4>
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:<br />
<br />
<ul>
<li>functions as parameters</li>
<li>functions with locked or queued parameters</li>
</ul>
<br />
Pretty small list, right! Well, to be honest, it's the list of known bugs. There are probably bugs we don't know about.<br />
<br />
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 <a href="http://en.wikipedia.org/wiki/Bootstrapping_(compilers)" target="">bootstrapping</a>. The executable it produces is able to compile other ParaSail programs.<br />
<br />
<h4>
Debugging Information</h4>
<div>
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.</div>
<div>
<br /></div>
<h4>
Syntax Highlighting on the Web with Pygments</h4>
<div>
<a href="http://pygments.org/">Pygments</a> 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.</div>
<div>
<br /></div>
<h4>
Static Analysis</h4>
<div>
Next, we're going to spend more time on static analysis, especially checking for nullness of objects and recognizing unused variables.</div>
<div>
<br /></div>
<h4>
OpenMP</h4>
<div>
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.</div>
Anonymoushttp://www.blogger.com/profile/08642892258221588380noreply@blogger.com3tag:blogger.com,1999:blog-8383004232931899216.post-44337437783936033802014-06-12T17:48:00.000-04:002014-06-12T17:48:49.139-04:00Linkers and Types and Built-ins! Oh, my!<div dir="ltr" style="text-align: left;" trbidi="on">
Hello, It's Justin again. See the previous blog post for a bit of context. (Hint: we're building the compiler)<br />
<br />
<h3>
Linking to the Built-ins</h3>
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).<br />
<br />
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.<br />
<br />
<h3>
Types</h3>
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<some_hashable_type> where we need to get the Hash operation for Some_Hashable_Type, and perhaps its representation for "null").</some_hashable_type><br />
<br />
Here's an example:<br />
<br />
<b>func</b> Count_Nulls(Numbers : Basic_Array<<b>optional</b> Univ_Integer>) -> Univ_Integer <b>is</b><br />
<b>var</b> Count := 0;<br />
<b>var</b> I := 1;<br />
<b>while</b> I <= Length(Numbers) <b>loop</b><br />
<b>if</b> Numbers[I] <b>is null then</b><br />
Count += 1;<br />
<b>end if</b>;<br />
I += 1;<br />
<b>end loop</b>;<br />
<b>return</b> Count;<br />
<b>end func</b> Count_Nulls;<br />
<br />
<b>func</b> main(Args : Basic_Array<Univ_String>) <b>is</b><br />
<b>var</b> A : Basic_Array<<b>optional</b> Univ_Integer> := Create(10, <b>null</b>);<br />
A[1] := 42;<br />
A[5] := 0;<br />
Print("There are ");<br />
Print(Count_Nulls(A));<br />
Println(" nulls");<br />
<b>end func</b> main;<br />
<br />
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].<br />
<br />
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.<br />
<br />
A very similar method is used to reconstruct the appropriate run-time representations for Univ_Strings and Univ_Enumerations from their stream representations.<br />
<h4>
Back to the example</h4>
<div>
First of all: It compiles and runs! Here's what it prints out:<br />
<br />
There are 8 nulls<br />
<br />
Woohoo!<br />
(that part was me)<br />
<br />
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<br />
<br />
<b>for</b> I := 1 <b>while</b> I < N <b>forward loop</b><br />
<b> block</b><br />
<b>continue loop with</b> I => I * 2;<br />
<b>||</b><br />
<b>continue loop with</b> I => I + 1;<br />
<b>end block</b>;<br />
<b>end loop</b>;<br />
<br />
While loops can be implemented with simple llvm 'br' instructions.<br />
<br />
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.<br />
<br /></div>
<h3>
Other Updates</h3>
<h4>
Main</h4>
<div>
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.</div>
<h4>
Reflection</h4>
"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.<br />
<h4>
Static Link</h4>
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.<br />
<br />
We're making tremendous headway on this compiler and I'm very excited about where we could reach by the end of this summer.</div>
Anonymoushttp://www.blogger.com/profile/08642892258221588380noreply@blogger.com1tag:blogger.com,1999:blog-8383004232931899216.post-91403473934189163182014-05-27T16:25:00.002-04:002014-05-27T16:25:49.965-04:00From an Interpreter to a CompilerMy name is Justin Hendrick and I'm an intern working on ParaSail for the summer. My first task is code generation.<br />
<br />
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 <a href="http://llvm.org/">llvm.org</a> and the <a href="http://llvm.org/docs/LangRef.html">reference manual</a>.<br />
<br />
So far, we can successfully compile simple functions that branch and do arithmetic on Univ_Integers and Univ_Reals.<br />
<br />
For example, this ParaSail max function:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"><b>func</b> Max(A : Univ_Integer; B : Univ_Integer) -> Univ_Integer <b>is</b></span><br />
<span style="font-family: Courier New, Courier, monospace;"> <b>if</b> A > B <b>then</b></span><br />
<span style="font-family: Courier New, Courier, monospace;"> <b>return</b> A;</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <b>else</b></span><br />
<span style="font-family: Courier New, Courier, monospace;"> <b>return</b> B;</span><br />
<span style="font-family: Courier New, Courier, monospace;"> <b>end if</b>; </span><br />
<span style="font-family: Courier New, Courier, monospace;"><b>end func</b> Max;</span><br />
<br />
Is converted to ParaSail Virtual Machine Intermediate Representation. See <a href="http://parasail-programming-language.blogspot.com/2010/11/virtual-machine-for-parasail-with.html">this post</a> for more details on the PSVM and the calling convention in use.<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"> ----- ParaSail Virtual Machine Instructions ---- </span><br />
<span style="font-family: Courier New, Courier, monospace;">Max: Routine # 720</span><br />
<span style="font-family: Courier New, Courier, monospace;">(A : Univ_Integer<>; B : Univ_Integer<>) -> Max : Univ_Integer<></span><br />
<span style="font-family: Courier New, Courier, monospace;">Uses_Queuing = FALSE</span><br />
<span style="font-family: Courier New, Courier, monospace;">Local_Area_Length = 17</span><br />
<span style="font-family: Courier New, Courier, monospace;">Start_Callee_Locals = 7</span><br />
<span style="font-family: Courier New, Courier, monospace;">Code_Length = 13</span><br />
<span style="font-family: Courier New, Courier, monospace;">(COPY_WORD_OP, Destination => (Local_Area, 5), Source => (Param_Area, 1))</span><br />
<span style="font-family: Courier New, Courier, monospace;">(COPY_WORD_OP, Destination => (Local_Area, 6), Source => (Param_Area, 2))</span><br />
<span style="font-family: Courier New, Courier, monospace;">(CALL_OP, Params => (Local_Area, 4), Static_Link => (Zero_Base, 5) = Univ_Integer<>, Call_Target => (Zero_Base, 59) = "=?")</span><br />
<span style="font-family: Courier New, Courier, monospace;">(STORE_INT_LIT_OP, Destination => (Local_Area, 5), Int_Value => 4)</span><br />
<span style="font-family: Courier New, Courier, monospace;">(CALL_OP, Params => (Local_Area, 3), Static_Link => (Zero_Base, 30) = Ordering<>, Call_Target => (Zero_Base, 19) = "to_bool")</span><br />
<span style="font-family: Courier New, Courier, monospace;">(IF_OP, If_Source => (Local_Area, 3), If_Condition => 2, Skip_If_False => 4)</span><br />
<span style="font-family: Courier New, Courier, monospace;">(COPY_WORD_OP, Destination => (Local_Area, 3), Source => (Param_Area, 1))</span><br />
<span style="font-family: Courier New, Courier, monospace;">(COPY_WORD_OP, Destination => (Param_Area, 0), Source => (Local_Area, 3))</span><br />
<span style="font-family: Courier New, Courier, monospace;">(RETURN_OP)</span><br />
<span style="font-family: Courier New, Courier, monospace;">(SKIP_OP, Skip_Count => 3)</span><br />
<span style="font-family: Courier New, Courier, monospace;">(COPY_WORD_OP, Destination => (Local_Area, 3), Source => (Param_Area, 2))</span><br />
<span style="font-family: Courier New, Courier, monospace;">(COPY_WORD_OP, Destination => (Param_Area, 0), Source => (Local_Area, 3))</span><br />
<span style="font-family: Courier New, Courier, monospace;">(RETURN_OP)</span><br />
<br />
After code generation and a pass through LLVM’s optimizer this becomes<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">define void @Max(i64* %_Static_Link, i64* %_Param_Area) {</span><br />
<span style="font-family: Courier New, Courier, monospace;"> %_source1 = getelementptr inbounds i64* %_Param_Area, i64 1</span><br />
<span style="font-family: Courier New, Courier, monospace;"> %_source_val1 = load i64* %_source1, align 8</span><br />
<span style="font-family: Courier New, Courier, monospace;"> %_source2 = getelementptr inbounds i64* %_Param_Area, i64 2</span><br />
<span style="font-family: Courier New, Courier, monospace;"> %_source_val2 = load i64* %_source2, align 8</span><br />
<span style="font-family: Courier New, Courier, monospace;"> %_result3 = icmp sgt i64 %_source_val1, %_source_val2</span><br />
<span style="font-family: Courier New, Courier, monospace;"> br i1 %_result3, label %_lbl7, label %_lbl11</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">_lbl7: ; preds = %0</span><br />
<span style="font-family: Courier New, Courier, monospace;"> store i64 %_source_val1, i64* %_Param_Area, align 8</span><br />
<span style="font-family: Courier New, Courier, monospace;"> ret void</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">_lbl11: ; preds = %0</span><br />
<span style="font-family: Courier New, Courier, monospace;"> store i64 %_source_val2, i64* %_Param_Area, align 8</span><br />
<span style="font-family: Courier New, Courier, monospace;"> ret void</span><br />
<span style="font-family: Courier New, Courier, monospace;">}</span><br />
<br />
And from there, LLVM can generate machine code for many architectures.<br />
<br />
The next steps are to enable calls to built-in functions, handle types other than Univ_Integer and Univ_Real, and implement Parallel Calls.<br />
<br />
We plan to make more frequent releases this summer than in the past.<br />
<br />
Stay tuned for more updates on the state of the compiler.Anonymoushttp://www.blogger.com/profile/08642892258221588380noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-45979679033689334332014-04-05T15:42:00.000-04:002014-04-05T15:42:13.834-04:00A simple and useful iterator pattern in ParaSail<div dir="ltr" style="text-align: left;" trbidi="on">
<b>ParaSail</b> has three basic iterator formats, with some sub-formats (unbolded "[ ... ]" indicate optional parts, unbolded "|" indicate alternatives, <b>bold</b> indicates reserved words or symbols that are part of the syntax itself):<br />
<span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"><br /></span></span>
<span style="font-size: small;"><span style="font-family: inherit;"> 1. Set iterator:</span></span><br />
<span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"><span style="font-size: small;"><b> for</b> I <b>in</b> Set [<b>forward</b> | <b>reverse</b> | <b>concurrent</b>] <b>loop</b> ...</span></span></span><br />
<span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"><br /></span></span>
<span style="font-size: small;"><span style="font-family: inherit;"> 2. Element iterator:</span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"><b> for</b> <b>each</b> E <b>of</b> Container [<b>forward</b> | <b>reverse</b> | <b>concurrent</b>] loop ...</span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> <span style="font-family: inherit;">or</span></span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> <b>for</b> <b>each</b> <b>[</b>K <b>=></b> V<b>]</b> <b>of</b> Container </span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> [<b>forward</b> | <b>reverse</b> | <b>concurrent</b>] loop ... </span></span><br />
<span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"><br /></span></span>
<span style="font-size: small;"><span style="font-family: inherit;"> 3. Value iterator:</span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> <b>for</b> V <b>:=</b> Initial [<b>then</b> Next_Value(V)] [<b>while</b> Predicate(V)] <b>loop</b> ...</span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> or</span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> <b>for</b> T <b>=></b> Root [<b>then</b> T.Left <b>|</b> T.Right] [<b>while</b> T <b>not null</b>]<b> loop</b> ... </span></span><br />
<span style="font-size: small;"><br /></span>
These iterators can be combined into a single loop by parenthesizing them; the loop quits as soon as any of the iterators completes:<br />
<br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> <b>for</b> (<b>each</b> E <b>of</b> Container; I <b>in</b> 1..100) <b>forward</b> <b>loop</b> ...</span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> <i> // Display up to 100 elements of Container</i></span></span><br />
<br />
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:<br />
<br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> <b>for</b> (<b>each</b> V <b>of</b> Vec; Sep := "[" <b>then</b> ", ") <b>forward</b> <b>loop</b></span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> Print(Sep | V);</span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> <b>end loop</b></span></span><br />
<span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"> Print("]")</span></span><br />
<br />
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.<br />
<br />
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 <a href="http://parasail-lang.org/">http://parasail-lang.org</a> .</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-76731758463722781552014-02-20T00:06:00.000-05:002014-02-20T00:06:22.119-05:00ParaSail Work Stealing speeds up<div dir="ltr" style="text-align: left;" trbidi="on">
We are now releasing revision 5.2 of the <b>ParaSail</b> compiler and interpreter, which incorporates a new implementation of <i>work stealing</i>. Links to both binaries and sources can be found at:<br />
<br />
<a href="http://parasail-lang.org/">http://parasail-lang.org</a><br />
<br />
in the <i>Documentation and Download</i> section of the web page.<br />
<br />
Here is the new entry in the release notes for revision 5.2:<br />
<br />
* [rev 5.2] <i>Re-implementation of work stealing to reduce contention between processors. Each server now has a private double-ended queue (deque) of pico-threads, along with the shared triplet of deques which has existed before. This produced another two times speedup (in addition to the rev 4.9 improvements), thereby speeding up execution by four times or more since rev 4.8. The main procedures for each language (ParaSail, Sparkel, etc.) have been refactored to share more common code. Allow a command-line flag "-servers nnn" to specify the number of heavy-weight server threads to use. Default is 6. Command can also be given interactively, as "servers nnn". Interactively it only works to increase the number; there is no way to shut down servers that already have been activated.</i><br />
<br /></div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-5567690618824116092014-02-19T12:18:00.001-05:002014-02-19T12:18:36.541-05:00Worklist Algorithms and Parallel Iterators<div dir="ltr" style="text-align: left;" trbidi="on">
<b>ParaSail</b> has some very general parallel iterator constructs. One of the more unusual involves the use of a <b>continue</b> statement to initiate a new iteration of an outer loop statement, as illustrated in this breadth-first search of a graph:<br />
<br />
<pre> <b>var</b> Seen : Array<Atomic<Boolean>, Indexed_By => Node_Id> :=
[for I in 1 .. |DGraph.G| => Create(#false)];
*Outer*
<b>for</b> Next_Set => Root_Set <b>loop</b> <i>// Start with the initial set of roots</i>
<b>for</b> N <b>in</b> Next_Set <b>concurrent</b> <b>loop</b> <i>// Look at each node in set</i>
<b>if</b> <b>not</b> Value(Seen[N]) <b>then</b>
Set_Value(Seen[N], #true);
<b>if</b> Is_Desired_Node(DGraph.G[N]) <b>then</b> <i>// Found a node</i>
<b>return</b> N;
<b>end</b> <b>if</b>;
<i>// Continue outer loop with successors of this node</i>
<b>continue</b> <b>loop</b> Outer <b>with</b> Next_Set => DGraph.G[N].Succs;
<b>end</b> <b>if</b>;
<b>end</b> <b>loop</b>;
<b>end</b> <b>loop</b> Outer;
<i>// No node found</i>
<b>return</b> <b>null</b>;</pre>
<div>
<br />
It has been a bit hard to explain what it means for an inner concurrent loop to <b>continue</b> an outer loop. More recently, we have developed an alternative explanation. The basic idea is to appeal to the notion of a <i>worklist</i> algorithm. Various (sequential) algorithms are organized around the use of a list of work items to be processed, with the overall algorithm continuing until the worklist is empty, or, for a search, until an item of interest is found. For example, the work-list approach to data flow analysis algorithms is described here:<br />
<ul style="text-align: left;">
<li><a href="http://en.wikipedia.org/wiki/Data-flow_analysis#The_work_list_approach">http://en.wikipedia.org/wiki/Data-flow_analysis#The_work_list_approach</a> </li>
</ul>
Here is another worklist-based algorithm, for solving a constraint satisfaction problem using the Arc Consistency approach:<br />
<ul style="text-align: left;">
<li> <a href="http://en.wikipedia.org/wiki/AC-3_algorithm">http://en.wikipedia.org/wiki/AC-3_algorithm</a></li>
</ul>
Finally, here is a breadth-first graph search algorithm, which uses a <i>work queue</i> instead of a work list:<br />
<ul style="text-align: left;">
<li><a href="http://en.wikipedia.org/wiki/Breadth-first_search">http://en.wikipedia.org/wiki/Breadth-first_search</a></li>
</ul>
</div>
<div>
So one way of explaining this kind of ParaSail iterator is as a built-in work-list-based iterator, where the loop keeps going until there are no more work items to process, and <b>continue</b> adds a new work-item to the worklist. This approach makes it clear that such iterators can work even if there is only one physical processor available, and also suggests that the work items are <i>not</i> full threads of control, but rather light-weight representations of some work to be done. This terminology of <i>work</i> <i>items</i> and <i>work list</i> or <i>work queue</i> also matches well with the terminology of the underlying <i>work</i> <i>stealing</i> scheduling mechanism in use.<br />
<br />
We used to refer to such ParaSail's parallel iterators as a <i>bag of threads</i>, but now it seems easier to describe each iterator as having its own list of work items (i.e. a <i>worklist)</i> and the loop keeps going until the worklist is empty, or until we encounter a <span style="font-family: "Courier New",Courier,monospace;"><b>return</b></span> or <span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"><b>exit</b></span></span> (aka <span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;"><b>break</b></span></span>) statement.<br />
<br />
One interesting detail at this point is that for a breadth-first search, you want the work list/queue to be processed in a FIFO manner, while for a depth-first search, you want to process the work list/queue as a stack, in a LIFO manner. The work-stealing scheduler we use does some of both, using FIFO when stealing, and LIFO when the work-items are served by the same core that generated them. This argues for perhaps giving more control to the programmer when using an explicit <b>continue</b> statement, to be able to specify FIFO or LIFO. However, it is not entirely clear if that added complexity is worthwhile.</div>
</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-16239228341044233592013-12-23T12:33:00.001-05:002013-12-24T09:51:01.320-05:00Concurrency vs. Parallelism<div dir="ltr" style="text-align: left;" trbidi="on">
Over the past few years there seems to have been an increasing number of discussions of the difference between concurrency and parallelism. These discussions didn't seem very convincing at first, but over time a useful distinction did begin to emerge. So here is another attempt at trying to distinguish these two:<br />
<ul style="text-align: left;">
<li><span style="font-family: inherit;"><span style="font-size: small;"><span style="color: black;"></span><span style="color: black; font-style: italic;">Concurrent</span><span style="color: black;"></span><span style="color: black;">
programming constructs allow a programmer to </span><span style="color: black; font-style: italic;">simplify</span><span style="color: black;"> their program by
using multiple (heavy-weight) threads to reflect the natural concurrency in the problem domain. Because restructuring the program in this way can provide significant benefits in understandability, relatively heavy weight constructs are acceptable. Performance is also not necessarily as critical, so long as it is predictable.</span></span></span></li>
<li><span style="font-family: inherit;"><span style="font-size: small;"><span style="color: black;"></span><span style="color: black; font-style: italic;">Parallel</span><span style="color: black;"></span><span style="color: black;">
programming constructs allow a programmer to </span><span style="color: black; font-style: italic;">divide
and conquer</span><span style="color: black;">
a problem, using multiple (light-weight) threads to work in parallel on independent parts of
the problem. Such restructuring does not necessarily simplify the program, and as such parallel programming constructs need to be relatively light weight, both syntactically and at
run-time. If the constructs introduce too much overhead, they defeat the purpose.</span></span></span><span style="font-family: inherit;"><span style="font-size: small;"><span style="color: black;"> </span></span></span></li>
</ul>
<span style="font-family: inherit;"><span style="font-size: small;"><span style="color: black;">Given sufficiently flexible parallel programming constructs, it is not clear that you also need traditional concurrent programming constructs. But it may be useful to provide some higher-level notion of <i>process,</i> which forgoes the single-threaded presumption of a <i>thread</i>, but brings some of the benefits from explicitly representing the natural concurrency of the problem domain within the programming language.</span></span></span><br />
<br />
<span style="font-family: inherit;"><span style="font-size: small;"><span style="color: black;"><b>ParaSail</b> is focused on providing <i>parallel</i> programming constructs, but <b>concurrent</b> objects are useful for more traditional concurrent programming approaches, particularly when coupled with explicit use of the "<b>||</b>" operator. It is an interesting question whether some higher-level <i>process</i>-like construct might be useful. </span></span></span><span style="font-family: inherit;"></span>
</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com7tag:blogger.com,1999:blog-8383004232931899216.post-22440744250868375412013-11-21T20:24:00.000-05:002013-11-21T20:24:12.475-05:00First release of Javallel, Parython; new release 5.1 of ParaSail and Sparkel<div dir="ltr" style="text-align: left;" trbidi="on">
The <b>ParaSail</b> family of languages is growing, with two more additions now available for experimentation. We have made a new release 5.1 which includes all four members of the family -- <i>ParaSail</i> itself, <i>Sparkel</i> based on the SPARK subset of Ada, <i>Javallel</i> based on Java, and <i>Parython</i> based on Python. Binaries plus examples for these are all available in a single (large) download:<br />
<br />
<a href="http://bit.ly/ps51bin">http://bit.ly/ps51bin</a><br />
<br />
As before, if you are interested in sources, visit:<br />
<br />
<a href="http://sparkel.org/">http://sparkel.org</a><br />
<br />
The biggest change in ParaSail was a rewrite of the <i>region-based storage manager</i> (actually, this same storage manager is used for all four languages), to dramatically reduce the contention between cores/processors related to storage management. The old implementation was slower, and nevertheless still had a number of race conditions. This one is faster and (knock on wood) free of (at least those ;-) race conditions.<br />
<br />
As far as how <i>Javallel</i> relates to <i>Java</i>, here are some of the key differences:<br />
<ol style="text-align: left;">
<li>Classes require a "<b>class</b> <b>interface</b>" to declare their visible operations and fields
</li>
<li>There is no notion of a "<b>this</b>" parameter -- all parameters must be declared
</li>
<li>There is no notion of "<b>static</b>" -- a method is effectively static if it doesn't have any parameters whose type matches the enclosing class; no variables are static</li>
<li>You only say "<b>public</b>" once, in the class, separating the private stuff (before the word "<b>public</b>") from the implementation of the visible methods.
</li>
<li>Semi-colons are optional at the end of a line
</li>
<li>Parentheses are optional around the condition of an "<b>if</b>"
</li>
<li>"for" statements use a different syntax; e.g:
<ul>
<li> <b>for</b> I <b>in</b> 1..10 [<b>forward</b> | <b>reverse </b>| <b>parallel</b>] { ... }
</li>
</ul>
</li>
<li>"{" and "}" are mandatory for all control structures
</li>
<li>You can give a name to the result of a method via: </li>
<ul>
<li>Vector<integer> createVec(...) <b>as</b> Result { ... Result = blah; ... } </integer></li>
</ul>
and then use that name (Result) inside as a variable whose final value is returned
<li>You have to say "T+" rather than simply "T" if you want to accept actual parameter that are of any subclass of T (aka <i>polymorphic</i>). "T" by itself only allows actuals of exactly class T.
</li>
<li>Object declarations must start with "<b>var</b>," "<b>final</b>," or "<b>ref</b>" corresponding to <i>variable</i> objects, <i>final</i> objects, or <i>ref</i> objects (short-lived renames).
</li>
<li>There are no special constructors; any method that returns a value of the enclosing is effectively a constructor; objects may be created inside a method using a tuple-like syntax "(a => 2, b => 3)" whose type is determined from context
</li>
<li>X.Foo(Y) is equivalent to Foo(X, Y)
</li>
<li>Top-level methods are permitted, to simplify creating a "main" method
</li>
<li>uses "<b>and</b> <b>then</b>" and "<b>or</b> <b>else</b>" instead of "&&" and "||"; uses "||" to introduce explicit parallelism.
</li>
<li>"<b>synchronized</b>" applies to classes, not to methods or blocks
</li>
<li>enumeration literals start with "#"</li>
</ol>
<div style="text-align: left;">
There are examples in javallel_examples/*.jl?, which should give a better idea of what
javallel is really like. Parython examples are in parython_examples/*.pr?
<br />
</div>
<br /></div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com1tag:blogger.com,1999:blog-8383004232931899216.post-48696269107812578002013-11-14T15:33:00.000-05:002013-11-14T15:33:47.065-05:00Using ParaSail as a Modeling Language for Distributed Systems<div dir="ltr" style="text-align: left;" trbidi="on">
The ACM HILT 2013 conference just completed in Pittsburgh, and we had some great tutorials, keynotes, and sessions on model-based engineering, as well as on formal methods applied to both modeling and programming languages. One of the biggest challenges identified was integrating complex systems with components defined in various modeling or domain-specific languages, along with an overall architecture, which might be specified in a language like AADL or SysML or might just be sketches on a whiteboard somewhere. A big part of the challenge is that different languages have different underlying semantic models, with different type systems, different notions of time, different concurrency and synchronization models (if any), etc. The programming language designer in me wants to somehow bring these various threads (so to speak) together in a well-defined semantic framework, ideally founded on a common underlying language.<br />
<br />
One way to start is by asking how can you "grow" a programming language into a modeling language (without killing it ;-)? <b>ParaSail</b> has some nice features that might fit well at the modeling level, in that its pointer-free, implicitly parallel control and data semantics are already at a relatively high level, and don't depend on a single-address-space view, nor a central-processor-oriented view. As an aside, Sebastian Burckhardt from Microsoft Research gave a nice talk on "cloud sessions" at the recent SPLASH/OOPSLA conference in Indianapolis (<a href="http://splashcon.org/2013/program/991">http://splashcon.org/2013/program/991</a>, <a href="http://research.microsoft.com/apps/pubs/default.aspx?id=163842">http://research.microsoft.com/apps/pubs/default.aspx?id=163842</a>), and we chatted afterward about what a perfect fit the ParaSail pointer-free type model was to the Cloud Sessions indefinitely-persistent data model. Modeling often abstracts away some of the details of the distribution and persistence of processing and data, so the friendliness of the ParaSail model to Cloud Sessions might also bode well for its friendliness to modeling of other kinds of long-lived distributed systems. <br />
<br />
ParaSail's basic model is quite simple, involving parameterized modules, with separate definition of interface and implementation, types as instantiations of modules, objects as instances of types, and operations defined as part of defining modules, operating on objects. Polymorphism is possible in that an object may be explicitly identified as having a <i>polymorphic</i> type (denoted by T+ rather than simply T) and then the object carries a run-time type identifier, and the object can hold a value of any type that implements the interface defined by the type T, including T itself (if T is not an abstract type), as well as types that provide in their interface all the same operations defined in T's interface.<br />
<br />
So how does this model relate to a modeling language like Simulink or a Statemate? Is a Simulink "block" a module, a type, an object, or an operation (or something entirely different)? What about a box on a state-machine chart? For Simulink, one straightforward answer is that a Simulink block is a ParaSail object. The associated type of the block object defines a set of operations or parameter values that determine how it is displayed, how it is simulated, how it is code-generated, how it is imported/exported using some XML-like representation, etc. A Simulink graph would be an object as well, being an instance of a directed graph type, with a polymorphic type, say "Simulink_Block+," being the type of the elements in the graph (e.g. DGraph<simulink_block>).</simulink_block><br />
<br />
Clearly it would be useful to define new block types using the Simulink-like modeling language itself, rather than having to "drop down" to the underlying programming language. One could imagine a predefined block type "User_Defined_Block" used to represent such blocks, where the various display/simulation/code-generation/import/export operations would be defined in a sub-language that is itself graphical, but relies on some additional (built-in) block types specifically designed for defining such lower-level operations. Performing code-generation on these graphs defining the various primitive operations of this new user-defined block type would ideally create code in the underlying programming language (e.g. ParaSail) that mimics closely what a (ParaSail) programmer might have written to define a new block type directly in the (ParaSail) programming language. This begins to become somewhat of a "meta" programming language, which always makes my head spin a little...<br />
<br />
A practical issue at the programming language level when you go this direction is that, what was a simple interface/implementation module model, may want to support "sub-modules" in various dimensions. In particular, there may be sets of operations associated with a given type devoted to relatively distinct problems, such as display vs. code generation, and it might be useful to allow both the interface, and certainly the implementation of a block-type-defining module to be broken up into sub-modules. The ParaSail design includes this notion, which we have called "interface extensions" (which is a bit ambiguous, so the term "interface add-on" might be clearer). These were described in:<br />
<a href="http://parasail-programming-language.blogspot.com/2010/08/eliminating-need-for-visitor-pattern-in.html">http://parasail-programming-language.blogspot.com/2010/08/eliminating-need-for-visitor-pattern-in.html</a><br />
but have not as of yet been implemented. Clearly interface add-ons, for say, [#display] or [#code_gen], could help separate out the parts of the definition of a given block type.<br />
<br />
A second dimension for creating sub-modules would be alternative implementations of the same interface, with automatic selection of the particular implementation based on properties of the parameters specified when the module is instantiated. In particular, each implementation might have its own instantiation "preconditions" which indicate what must be true about the actual module parameters provided before a given implementation is chosen. In addition, there needs to be some sort of a preference rule to use when more than one implementations' preconditions are satisfied by a given instantiation. For example, presume we have one implementation of an Integer interface that handles 32-bit ranges of integers, a second that handles 64-bit ranges, and one that handles infinite range. Clearly the 32-bit implementation would have a precondition that the range required be within +/- 2^31, the 64-bit one would require the range be within +/- 2^63, and the infinite-range-handling implementation would have no precondition. If we were to instantiate this Integer module with a 25-bit range, the preconditions of all three of the implementations would be satisfied, but there would presumably be a preference to use the 32-bit implementation over the other two. The approach we have considered for this is to allow a numeric "preference" level to be specified when providing an implementation of a module along with the implementation "preconditions," with the default level being "0" and the default precondition being "#true." The compiler would choose the implementation with the maximum preference level with satisfied preconditions. It would complain if there were a tie, requiring the user to specify explicitly which implementation of the module is to be chosen at the point of instantiation.</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-12604787250504478452013-11-06T14:30:00.000-05:002013-11-06T14:30:32.336-05:00Tech talk and Tutorial at SPLASH 2013 on parallel programming<div dir="ltr" style="text-align: left;" trbidi="on">
I gave an 80-minute "tech talk" and a 3-hour tutorial on parallel programming last week at SPLASH 2013 in Indianapolis. The audiences were modest but enthusiastic. <br />
<br />
The tech talk was entitled: <br />
<i><br /></i>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<i> Living without Pointers: Bringing Value Semantics to Object-Oriented Parallel Programming</i> </div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<br /></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
Here is the summary:</div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<br /></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<span style="font-size: x-small;"><i>The heavy use of pointers in modern object-oriented programming
languages interferes with the ability to adapt computations to the new
distributed and/or multicore architectures. This tech talk will
introduce an alternative pointer-free approach to object-oriented
programming, which dramatically simplifies adapting computations to the
new hardware architectures. This tech talk will illustrate the
pointer-free approach by demonstrating the transformation of two popular
object-oriented languages, one compiled, and one scripting, into
pointer-free languages, gaining easier adaptability to distributed
and/or multicore architectures, while retaining power and ease of use.</i></span></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<br /></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
Here is a link to the presentation: <a href="http://bit.ly/sp13pf">http://bit.ly/sp13pf</a></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<br /></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
The tutorial was entitled:</div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<br /></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<i> Multicore Programming using Divide-and-Conquer and Work Stealing</i></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<br /></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
Here is the summary for the tutorial:<i> </i></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<br /><i><span style="font-size: x-small;">This tutorial will introduce attendees to the various paradigms for
creating algorithms that take advantage of the growing number of
multicore processors, while avoiding the overhead of excessive
synchronization overhead. Many of these approaches build upon the basic
divide-and-conquer approach, while others might be said to use a
multiply-and-conquer paradigm. Attendees will also learn the theory and
practice of "work stealing," a multicore scheduling approach which is
being adopted in numerous multicore languages and frameworks, and how
classic work-list algorithms can be restructured to take best advantage
of the load balancing inherent in work stealing. Finally, the tutorial
will investigate some of the tradeoffs associated with different
multicore storage management approaches, including task-local garbage
collection and region-based storage management.</span></i></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
</div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
Here is a link to the presentation: <a href="http://bit.ly/sp13mc">http://bit.ly/sp13mc</a> </div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<br /></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
Comments welcome!</div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
<br /></div>
<div class="contentheadingprogram" style="text-align: left;" width="100%">
-Tuck</div>
</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-59450834180673965802013-09-16T17:47:00.000-04:002013-09-16T17:47:04.655-04:00Parallelizing Python and Java<div dir="ltr" style="text-align: left;" trbidi="on">
Designing and implementing <b>ParaSail</b> has been a fascinating process. Achieving parallelism and safety at the same time by eliminating rather than adding features has worked out better than we originally expected. One of the lessons of the process has been that just a small number of key ideas are sufficient to achieve safe and easy parallelism. Probably the biggest is the <i>elimination of pointers</i>, with the substitution of <i>expandable objects</i>. The other big one is the elimination of direct <i>access to global variables</i>, instead requiring that a variable be <i>passed as a (<b>var</b> or <b>in out</b>) parameter</i> if a function is going to update it. Other important ones include the <i>elimination of parameter aliasing</i>, and the <i>replacement of exception handling</i> with a combination of more <i>pre-condition checking</i> at compile time and a more task-friendly <i>event handling</i> mechanism at run time. <br />
<br />
So the question now is whether some of these same key ideas can be applied to <i>existing</i> languages, to produce something with much the same look and feel of the original, while moving toward a much more <i>parallel-, multicore-, human-friendly semantics</i>.<br />
<br />
Over the past year we have been working on a language inspired by the verifiable SPARK subset of Ada, now tentatively dubbed <i>Sparkel</i> (for <i>ELegant, parallEL, SPARK</i>). For those interested, this experimental language now has its own website: <br />
<br />
<a href="http://www.sparkel.org/">http://www.sparkel.org</a><br />
<br />
Sparkel has essentially all of the power of ParaSail, but with a somewhat more SPARK-like/Ada-like look and feel. We will be giving a talk on Sparkel at the upcoming <i>HILT 2013</i> conference on <i>High Integrity Language Technology</i> in Pittsburgh in November:<br />
<br />
<a href="http://www.sigada.org/conf/hilt2013">http://www.sigada.org/conf/hilt2013</a><br />
<br />
<i>HILT 2013</i> is open for <i>registration</i>, and it promises to be a great conference, with great talks, tutorials, and panels about <i>model checking</i>, <i>model-based engineering</i>, <i>formal methods</i>, <i>SMT solvers</i>, <i>safe parallelism</i>, etc. (disclaimer -- please note the name of the program chair).<br />
<br />
At the upcoming <i>OOPSLA/SPLASH</i> conference, we are giving a talk about applying these same principles to <i>Python</i> and <i>Java</i>. Super-secret code names for the results of this effort are <i>Parython</i> and <i>Javallel</i>. The announcement of this talk is on the <i>splashcon.org</i> web site:<br />
<br />
<a href="http://splashcon.org/2013/program/tutorials-tech-talks/853-living-without-pointers-bringing-value-semantics-to-object-oriented-parallel-programming">http://splashcon.org/2013/program/tutorials-tech-talks/853-living-without-pointers-bringing-value-semantics-to-object-oriented-parallel-programming</a><br />
<br />
If you are coming to OOPSLA/SPLASH, please stop by to hear the results. We will also be adding entries over the next couple of months about some of the lessons learned in working to create a safe parallel language when starting quite explicitly from an existing language.</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com19tag:blogger.com,1999:blog-8383004232931899216.post-67944890580188532972013-09-12T22:32:00.000-04:002013-09-12T22:32:15.932-04:00Revision 4.7 of ParaSail alpha release now available<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="post-header">
</div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
We are pleased to release alpha revision 4.7 of the <b>ParaSail</b> compiler and virtual machine, available at the same URL:<br />
<br />
<a href="http://bit.ly/Mx9DRb">http://bit.ly/Mx9DRb</a></div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
</div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
This release includes a large number of <i>bug fixes</i>, plus the following <i>enhancements</i>:</div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
</div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
More support for operations on <i>polymorphic</i> types, including binary operations, where it is an error if the two operands have different underlying types, unless the operator is "=?". "=?" is a special case, where rather than an error, it returns #unordered if two polymorphic operands have different underlying types. This now allows us to define a type like Set<hashable> and have it work as desired, that is, as a Set holding (almost) any type.<br /><br />We have a <i>preference</i> now for <i>non-generic</i> operations when there would otherwise be ambiguity between a normal operation and a generic operation of the same name. This is relevant for the "|" operator on Univ_String. We have now added To_String and From_String on Univ_String (these are identity operations), which means Univ_String now implements the "Imageable<>" interface. The new preference rules prevents this from creating ambiguity on <univ-string> | <univ-string>.<br /><br />We know allow {> ... <} for annotations as a substitute for { ... }. This will allow us to eventually use { ... } for Set/Map constructors in the PARython dialect. The new {> ... <} syntax makes annotations a bit more obvious, which seems like a good thing.<br /><br />Even when still using "then"/"is"/"loop"/"of" instead of ":", we have made "end blah" <i>optional</i>. Presumably project-specific rules might require "end blah" if the construct is too many lines long (e.g. more than 20 lines).<br /><br /><i>Highlighting</i> information for the ConTEXT source text editor is under share/tools/... in a file named ConTEXT_ParaSail.chl courtesy of ParaSail user Arie van Wingerden. Similar information for the "geshi" highlighting system (used by WikiPedia) is in a file called geshi_parasail.php.<br /><br /><i>Case statements</i> over <i>polymorphic</i> objects are now supported where the case choice has an associated identifier, such as in:<br /><br /> var E : Expr+ := ...<br /> case E of<br /> [L : Leaf] => ...<br /> [U : Unary] => ...<br /> [B : Binary] => ...<br /> [..] =><br /> end case;<br /><br />Note that the specified types for the case choices must be non-polymorphic types at the moment. In a later release we will support having choices with polymorphic types, such as:<br /><br /> [SE : Simple_Expr+] => ...<br /> <br />where presumably Simple_Expr is an extension of Expr.<br /><br />We have added <i>function types</i>, of the form:</univ-string></univ-string></hashable></div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
<br /> func(X : Integer; Y : Float) -> Integer</div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
<br />Basically the same syntax as a "func" declaration but without the func's identifier. To declare a "func" that takes another "func" as a parameter, you would now use syntax like:</div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
<br /> func Apply<br /> (Op : func(X : Integer) -> Integer; S : Vector<integer>)<br /> -> Vector<integer></integer></integer></div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
<br />rather than the former syntax:</div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
<br /> func Apply<br /> (func Op(X : Integer) -> Integer; S : Vector<integer>)<br /> -> Vector<integer><br /><br />The syntax for <i>lambda expressions</i> has been simplified, so you only specify the names of the inputs, with no mention of the types of the inputs or the outputs. For example:<br /><br /> lambda (Y) -> 2*Y<br /> <br />is a lambda expression that doubles its input. A lambda expr can be passed as a parameter so long as the type of the formal parameter is a compatible "func" type. So for example, given the above definition of "Apply", you could write:<br /><br /> Apply (lambda(Y)->2*Y, [1, 2, 3])<br /><br />and expect to get "[2, 4, 6]" as the result (presuming "Apply" does the natural thing).</integer></integer></div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
</div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
We now <i>share the lock</i> between a polymorphic object and the non-polymorphic object it contains; we also share the lock between object and its parent part, if any. Handle "continue loop"s that exit blocks. Source code has been restructured to more easily handle new parser using same underlying language semantics, to support "Parython" and other language parallelization efforts.<br /><br />When a "<i>new</i>" type is declared (type T is new Integer<...>) we allow <i>additional operations</i> to be declared immediately thereafter in the same scope, and have them be visible wherever the type is later used, just as though a new module had been defined as an extension of the old module, and the new operations had been declared inside that new module.</div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
<br /></div>
<div class="post-body entry-content" id="post-body-4374683955894713267" itemprop="description articleBody">
When an expression <i>does not resolve</i>, we now provide <i>additional diagnostics</i> to help explain why.</div>
</div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0tag:blogger.com,1999:blog-8383004232931899216.post-30753364470819872622013-07-03T11:58:00.001-04:002013-07-03T11:58:29.619-04:00ParaSail web site now available<div dir="ltr" style="text-align: left;" trbidi="on">
We now have a (non-blog) web site for <b>ParaSail</b>:<br />
<br />
<a href="http://www.parasail-lang.org/">http://www.parasail-lang.org</a><br />
<br />
We will use this in the future as the official starting point for reaching resources for ParaSail, and in particular, getting to the latest documentation and downloads. We will also be creating some examples, and ideally an online <i>Read-Eval-Print-Loop</i> (REPL) for trying your own examples. If you have questions or comments about this new website, the Google Group for ParaSail is the best place to post those comments/questions:<br />
<br />
<a href="http://groups.google.com/group/parasail-programming-language">http://groups.google.com/group/parasail-programming-language</a></div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com3tag:blogger.com,1999:blog-8383004232931899216.post-18462553392376856952013-04-18T23:15:00.000-04:002013-04-19T22:58:32.869-04:00Systems Programming with Go, Rust, and ParaSailHere is a paper that goes with the talk I am giving this coming Tuesday, April 23 at the DESIGN West, aka Embedded Systems Conference, in San Jose, on a comparison between <b>Go</b>, <b>Rust</b>, and <b>ParaSail</b>.<br />
<br />
If you are in the Bay Area, come on down. The talk is ESC-218, on Tuesday April 23 from 2:00-3:00PM in Salon 3: <a href="http://www.ubmdesign.com/sanjose/schedule-builder/session-id/98">http://www.ubmdesign.com/sanjose/schedule-builder/session-id/98</a><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_fuVK2-iEWwmP5FfNbYgezRrlKPlyA1hga6nHkqHMGW4QvXLqbtZkLQRXMmcjAvdIBL8iAjyrV5v_kbmL_hRIOh0ZQl1nWfLSBigIn7-2jiOEPoo0DBFhCool2rtJHwAln8G23wVxIeSu/s1600/DesignWest_promo_presenter125x125.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_fuVK2-iEWwmP5FfNbYgezRrlKPlyA1hga6nHkqHMGW4QvXLqbtZkLQRXMmcjAvdIBL8iAjyrV5v_kbmL_hRIOh0ZQl1nWfLSBigIn7-2jiOEPoo0DBFhCool2rtJHwAln8G23wVxIeSu/s1600/DesignWest_promo_presenter125x125.gif" /></a></div>
<br />
<i><b>NOTE:</b> Some browsers are having trouble with this version of the paper. It was cut and pasted from a Word document, which is always dicey. A PDF version of this paper is available on the ParaSail Google Group:</i><br />
<br />
<a href="http://groups.google.com/group/parasail-programming-language" target="_blank">http://groups.google.com/group/parasail-programming-language</a><br />
<br />
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Courier New";
panose-1:2 7 3 9 2 2 5 2 4 4;
mso-font-charset:0;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 0 0 0 1 0;}
@font-face
{font-family:Wingdings;
panose-1:2 0 5 0 0 0 0 0 0 0;
mso-font-charset:2;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:0 268435456 0 0 -2147483648 0;}
@font-face
{font-family:Wingdings;
panose-1:2 0 5 0 0 0 0 0 0 0;
mso-font-charset:2;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:0 268435456 0 0 -2147483648 0;}
@font-face
{font-family:"Trebuchet MS";
panose-1:2 11 6 3 2 2 2 2 2 4;
mso-font-charset:0;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 0 0 0 1 0;}
@font-face
{font-family:"Lucida Console";
panose-1:2 11 6 9 4 5 4 2 2 4;
mso-font-charset:0;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 0 0 0 1 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-unhide:no;
mso-style-qformat:yes;
mso-style-parent:"";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.MsoFooter, li.MsoFooter, div.MsoFooter
{mso-style-noshow:yes;
mso-style-unhide:no;
mso-style-link:"Footer Char";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
tab-stops:center 3.0in right 6.0in;
font-size:12.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{mso-style-unhide:no;
color:blue;
mso-themecolor:hyperlink;
text-decoration:underline;
text-underline:single;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-noshow:yes;
mso-style-priority:99;
color:purple;
mso-themecolor:followedhyperlink;
text-decoration:underline;
text-underline:single;}
p.SIGPLANAbstractheading, li.SIGPLANAbstractheading, div.SIGPLANAbstractheading
{mso-style-name:"SIGPLAN Abstract heading";
mso-style-unhide:no;
mso-style-next:"SIGPLAN Paragraph 1";
margin-top:0in;
margin-right:0in;
margin-bottom:5.0pt;
margin-left:0in;
text-indent:0in;
line-height:12.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
page-break-after:avoid;
mso-outline-level:1;
mso-list:l3 level1 lfo2;
mso-hyphenate:none;
tab-stops:list 0in;
font-size:11.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
font-weight:bold;
mso-bidi-font-weight:normal;}
p.SIGPLANSectionheading, li.SIGPLANSectionheading, div.SIGPLANSectionheading
{mso-style-name:"SIGPLAN Section heading";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Basic";
mso-style-next:"SIGPLAN Paragraph 1";
margin-top:6.0pt;
margin-right:0in;
margin-bottom:5.0pt;
margin-left:0in;
text-indent:0in;
line-height:13.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
page-break-after:avoid;
mso-outline-level:1;
mso-list:l1 level1 lfo1;
mso-hyphenate:none;
font-size:11.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
font-weight:bold;
mso-bidi-font-weight:normal;}
p.SIGPLANBasic, li.SIGPLANBasic, div.SIGPLANBasic
{mso-style-name:"SIGPLAN Basic";
mso-style-unhide:no;
mso-style-parent:"";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANParagraph1, li.SIGPLANParagraph1, div.SIGPLANParagraph1
{mso-style-name:"SIGPLAN Paragraph 1";
mso-style-unhide:no;
mso-style-next:"SIGPLAN Paragraph";
margin:0in;
margin-bottom:.0001pt;
text-align:justify;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
font-size:9.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANParagraph, li.SIGPLANParagraph, div.SIGPLANParagraph
{mso-style-name:"SIGPLAN Paragraph";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Paragraph 1";
margin:0in;
margin-bottom:.0001pt;
text-align:justify;
text-indent:12.0pt;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
font-size:9.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
span.FooterChar
{mso-style-name:"Footer Char";
mso-style-noshow:yes;
mso-style-unhide:no;
mso-style-locked:yes;
mso-style-link:Footer;
mso-ansi-font-size:12.0pt;}
p.SIGPLANSubsectionheading, li.SIGPLANSubsectionheading, div.SIGPLANSubsectionheading
{mso-style-name:"SIGPLAN Subsection heading";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Section heading";
mso-style-next:"SIGPLAN Paragraph 1";
margin-top:9.0pt;
margin-right:0in;
margin-bottom:5.0pt;
margin-left:1.0in;
text-indent:-.25in;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
page-break-after:avoid;
mso-outline-level:2;
mso-list:l3 level2 lfo2;
mso-hyphenate:none;
tab-stops:list 1.0in;
font-size:9.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
font-weight:bold;
mso-bidi-font-weight:normal;}
p.SIGPLANAuthorname, li.SIGPLANAuthorname, div.SIGPLANAuthorname
{mso-style-name:"SIGPLAN Author name";
mso-style-unhide:no;
mso-style-next:"SIGPLAN Author affiliation";
margin-top:0in;
margin-right:0in;
margin-bottom:1.0pt;
margin-left:0in;
text-align:center;
line-height:13.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:11.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANAuthoraffiliation, li.SIGPLANAuthoraffiliation, div.SIGPLANAuthoraffiliation
{mso-style-name:"SIGPLAN Author affiliation";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Author name";
mso-style-next:"SIGPLAN Author email";
margin-top:5.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
mso-add-space:auto;
text-align:center;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:9.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANAuthoraffiliationCxSpFirst, li.SIGPLANAuthoraffiliationCxSpFirst, div.SIGPLANAuthoraffiliationCxSpFirst
{mso-style-name:"SIGPLAN Author affiliationCxSpFirst";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Author name";
mso-style-next:"SIGPLAN Author email";
mso-style-type:export-only;
margin-top:5.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
mso-add-space:auto;
text-align:center;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:9.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANAuthoraffiliationCxSpMiddle, li.SIGPLANAuthoraffiliationCxSpMiddle, div.SIGPLANAuthoraffiliationCxSpMiddle
{mso-style-name:"SIGPLAN Author affiliationCxSpMiddle";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Author name";
mso-style-next:"SIGPLAN Author email";
mso-style-type:export-only;
margin:0in;
margin-bottom:.0001pt;
mso-add-space:auto;
text-align:center;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:9.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANAuthoraffiliationCxSpLast, li.SIGPLANAuthoraffiliationCxSpLast, div.SIGPLANAuthoraffiliationCxSpLast
{mso-style-name:"SIGPLAN Author affiliationCxSpLast";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Author name";
mso-style-next:"SIGPLAN Author email";
mso-style-type:export-only;
margin:0in;
margin-bottom:.0001pt;
mso-add-space:auto;
text-align:center;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:9.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANAuthoremail, li.SIGPLANAuthoremail, div.SIGPLANAuthoremail
{mso-style-name:"SIGPLAN Author email";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Author affiliation";
mso-style-next:"SIGPLAN Basic";
margin-top:2.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
text-align:center;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:8.0pt;
mso-bidi-font-size:9.0pt;
font-family:"Trebuchet MS";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANSubtitle, li.SIGPLANSubtitle, div.SIGPLANSubtitle
{mso-style-name:"SIGPLAN Subtitle";
mso-style-unhide:no;
mso-style-next:"SIGPLAN Basic";
margin-top:6.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
text-align:center;
line-height:18.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:14.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
font-weight:bold;
mso-bidi-font-weight:normal;}
p.SIGPLANParagraphSubparagraphheading, li.SIGPLANParagraphSubparagraphheading, div.SIGPLANParagraphSubparagraphheading
{mso-style-name:"SIGPLAN Paragraph\/Subparagraph heading";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Paragraph 1";
mso-style-next:"SIGPLAN Paragraph";
margin-top:7.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
text-align:justify;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-outline-level:4;
font-size:9.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
span.SIGPLANParagraphheading
{mso-style-name:"SIGPLAN Paragraph heading";
mso-style-unhide:no;
mso-style-parent:"";
font-weight:bold;
mso-bidi-font-weight:normal;
font-style:italic;
mso-bidi-font-style:normal;}
p.SIGPLANReferencesheading, li.SIGPLANReferencesheading, div.SIGPLANReferencesheading
{mso-style-name:"SIGPLAN References heading";
mso-style-unhide:no;
mso-style-next:"SIGPLAN Reference";
margin-top:6.0pt;
margin-right:0in;
margin-bottom:5.0pt;
margin-left:0in;
text-indent:0in;
line-height:13.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
page-break-after:avoid;
mso-outline-level:1;
mso-list:l2 level1 lfo3;
mso-hyphenate:none;
tab-stops:list 0in;
font-size:11.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
font-weight:bold;
mso-bidi-font-weight:normal;}
p.SIGPLANReference, li.SIGPLANReference, div.SIGPLANReference
{mso-style-name:"SIGPLAN Reference";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Paragraph 1";
margin-top:0in;
margin-right:0in;
margin-bottom:4.0pt;
margin-left:17.0pt;
text-align:justify;
text-indent:-17.0pt;
line-height:9.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
font-size:8.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
span.SIGPLANCode
{mso-style-name:"SIGPLAN Code";
mso-style-unhide:no;
mso-style-parent:"";
mso-ansi-font-size:8.0pt;
font-family:"Lucida Console";
mso-ascii-font-family:"Lucida Console";
mso-hansi-font-family:"Lucida Console";}
.MsoChpDefault
{mso-style-type:export-only;
mso-default-props:yes;
font-size:10.0pt;
mso-ansi-font-size:10.0pt;
mso-bidi-font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in .75in 1.0in .75in;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-paper-source:0;}
div.WordSection1
{page:WordSection1;}
@page WordSection2
{size:8.5in 11.0in;
margin:1.0in .75in 1.0in .75in;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-columns:2 even 24.0pt;
mso-paper-source:0;}
div.WordSection2
{page:WordSection2;}
@page WordSection3
{size:8.5in 11.0in;
margin:1.0in .75in 1.0in .75in;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-paper-source:0;}
div.WordSection3
{page:WordSection3;}
/* List Definitions */
@list l0
{mso-list-id:145319201;
mso-list-type:hybrid;
mso-list-template-ids:-545126026 67698689 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:.25in;
text-indent:-.25in;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:.75in;
text-indent:-.25in;
font-family:"Courier New";
mso-bidi-font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:1.25in;
text-indent:-.25in;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:1.75in;
text-indent:-.25in;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:2.25in;
text-indent:-.25in;
font-family:"Courier New";
mso-bidi-font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:2.75in;
text-indent:-.25in;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:3.25in;
text-indent:-.25in;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:3.75in;
text-indent:-.25in;
font-family:"Courier New";
mso-bidi-font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:4.25in;
text-indent:-.25in;
font-family:Wingdings;}
@list l1
{mso-list-id:756485799;
mso-list-template-ids:162827036;}
@list l1:level1
{mso-level-style-link:"SIGPLAN Section heading";
mso-level-suffix:none;
mso-level-text:"%1\. ";
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:0in;
text-indent:0in;}
@list l1:level2
{mso-level-suffix:none;
mso-level-text:"%1\.%2 ";
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:0in;
text-indent:0in;}
@list l1:level3
{mso-level-suffix:none;
mso-level-text:"%1\.%2\.%3 ";
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:.5in;
text-indent:-.5in;}
@list l1:level4
{mso-level-text:"%1\.%2\.%3\.%4";
mso-level-tab-stop:.5in;
mso-level-number-position:left;
margin-left:.5in;
text-indent:-.5in;}
@list l1:level5
{mso-level-text:"%1\.%2\.%3\.%4\.%5";
mso-level-tab-stop:.75in;
mso-level-number-position:left;
margin-left:.75in;
text-indent:-.75in;}
@list l1:level6
{mso-level-text:"%1\.%2\.%3\.%4\.%5\.%6";
mso-level-tab-stop:.75in;
mso-level-number-position:left;
margin-left:.75in;
text-indent:-.75in;}
@list l1:level7
{mso-level-text:"%1\.%2\.%3\.%4\.%5\.%6\.%7";
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
margin-left:1.0in;
text-indent:-1.0in;}
@list l1:level8
{mso-level-text:"%1\.%2\.%3\.%4\.%5\.%6\.%7\.%8";
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
margin-left:1.0in;
text-indent:-1.0in;}
@list l1:level9
{mso-level-text:"%1\.%2\.%3\.%4\.%5\.%6\.%7\.%8\.%9";
mso-level-tab-stop:1.25in;
mso-level-number-position:left;
margin-left:1.25in;
text-indent:-1.25in;}
@list l2
{mso-list-id:1644460410;
mso-list-type:hybrid;
mso-list-template-ids:-377845136 -1784543178 67567641 67567643 67567631 67567641 67567643 67567631 67567641 67567643;}
@list l2:level1
{mso-level-number-format:none;
mso-level-style-link:"SIGPLAN References heading";
mso-level-text:References;
mso-level-tab-stop:0in;
mso-level-number-position:left;
margin-left:0in;
text-indent:0in;}
@list l2:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:1.5in;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:3.0in;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:4.5in;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l3
{mso-list-id:1804500217;
mso-list-type:hybrid;
mso-list-template-ids:1316771182 -1213953032 67567641 67567643 67567631 67567641 67567643 67567631 67567641 67567643;}
@list l3:level1
{mso-level-number-format:none;
mso-level-style-link:"SIGPLAN Abstract heading";
mso-level-text:Abstract;
mso-level-tab-stop:0in;
mso-level-number-position:left;
margin-left:0in;
text-indent:0in;}
@list l3:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l3:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:1.5in;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l3:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l3:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:3.0in;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l3:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l3:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:4.5in;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
</style>
<br />
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Courier New";
panose-1:2 7 3 9 2 2 5 2 4 4;
mso-font-charset:0;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 0 0 0 1 0;}
@font-face
{font-family:Wingdings;
panose-1:2 0 5 0 0 0 0 0 0 0;
mso-font-charset:2;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:0 268435456 0 0 -2147483648 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;
mso-font-charset:0;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 0 0 0 1 0;}
@font-face
{font-family:"Trebuchet MS";
panose-1:2 11 6 3 2 2 2 2 2 4;
mso-font-charset:0;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 0 0 0 1 0;}
@font-face
{font-family:"Lucida Console";
panose-1:2 11 6 9 4 5 4 2 2 4;
mso-font-charset:0;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 0 0 0 1 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-unhide:no;
mso-style-qformat:yes;
mso-style-parent:"";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.MsoFooter, li.MsoFooter, div.MsoFooter
{mso-style-noshow:yes;
mso-style-unhide:no;
mso-style-link:"Footer Char";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
tab-stops:center 3.0in right 6.0in;
font-size:12.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{mso-style-unhide:no;
color:blue;
mso-themecolor:hyperlink;
text-decoration:underline;
text-underline:single;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-noshow:yes;
mso-style-priority:99;
color:purple;
mso-themecolor:followedhyperlink;
text-decoration:underline;
text-underline:single;}
p.SIGPLANAbstractheading, li.SIGPLANAbstractheading, div.SIGPLANAbstractheading
{mso-style-name:"SIGPLAN Abstract heading";
mso-style-unhide:no;
mso-style-next:"SIGPLAN Paragraph 1";
margin-top:0in;
margin-right:0in;
margin-bottom:5.0pt;
margin-left:0in;
text-indent:0in;
line-height:12.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
page-break-after:avoid;
mso-outline-level:1;
mso-list:l3 level1 lfo2;
mso-hyphenate:none;
tab-stops:list 0in;
font-size:11.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
font-weight:bold;
mso-bidi-font-weight:normal;}
p.SIGPLANSectionheading, li.SIGPLANSectionheading, div.SIGPLANSectionheading
{mso-style-name:"SIGPLAN Section heading";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Basic";
mso-style-next:"SIGPLAN Paragraph 1";
margin-top:6.0pt;
margin-right:0in;
margin-bottom:5.0pt;
margin-left:0in;
text-indent:0in;
line-height:13.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
page-break-after:avoid;
mso-outline-level:1;
mso-list:l1 level1 lfo1;
mso-hyphenate:none;
font-size:11.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
font-weight:bold;
mso-bidi-font-weight:normal;}
p.SIGPLANBasic, li.SIGPLANBasic, div.SIGPLANBasic
{mso-style-name:"SIGPLAN Basic";
mso-style-unhide:no;
mso-style-parent:"";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANParagraph1, li.SIGPLANParagraph1, div.SIGPLANParagraph1
{mso-style-name:"SIGPLAN Paragraph 1";
mso-style-unhide:no;
mso-style-next:"SIGPLAN Paragraph";
margin:0in;
margin-bottom:.0001pt;
text-align:justify;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
font-size:9.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANParagraph, li.SIGPLANParagraph, div.SIGPLANParagraph
{mso-style-name:"SIGPLAN Paragraph";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Paragraph 1";
margin:0in;
margin-bottom:.0001pt;
text-align:justify;
text-indent:12.0pt;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
font-size:9.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
span.FooterChar
{mso-style-name:"Footer Char";
mso-style-noshow:yes;
mso-style-unhide:no;
mso-style-locked:yes;
mso-style-link:Footer;
mso-ansi-font-size:12.0pt;}
p.SIGPLANSubsectionheading, li.SIGPLANSubsectionheading, div.SIGPLANSubsectionheading
{mso-style-name:"SIGPLAN Subsection heading";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Section heading";
mso-style-next:"SIGPLAN Paragraph 1";
margin-top:9.0pt;
margin-right:0in;
margin-bottom:5.0pt;
margin-left:1.0in;
text-indent:-.25in;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
page-break-after:avoid;
mso-outline-level:2;
mso-list:l3 level2 lfo2;
mso-hyphenate:none;
tab-stops:list 1.0in;
font-size:9.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
font-weight:bold;
mso-bidi-font-weight:normal;}
p.SIGPLANAuthorname, li.SIGPLANAuthorname, div.SIGPLANAuthorname
{mso-style-name:"SIGPLAN Author name";
mso-style-unhide:no;
mso-style-next:"SIGPLAN Author affiliation";
margin-top:0in;
margin-right:0in;
margin-bottom:1.0pt;
margin-left:0in;
text-align:center;
line-height:13.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:11.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANAuthoraffiliation, li.SIGPLANAuthoraffiliation, div.SIGPLANAuthoraffiliation
{mso-style-name:"SIGPLAN Author affiliation";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Author name";
mso-style-next:"SIGPLAN Author email";
margin-top:5.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
mso-add-space:auto;
text-align:center;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:9.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANAuthoraffiliationCxSpFirst, li.SIGPLANAuthoraffiliationCxSpFirst, div.SIGPLANAuthoraffiliationCxSpFirst
{mso-style-name:"SIGPLAN Author affiliationCxSpFirst";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Author name";
mso-style-next:"SIGPLAN Author email";
mso-style-type:export-only;
margin-top:5.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
mso-add-space:auto;
text-align:center;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:9.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANAuthoraffiliationCxSpMiddle, li.SIGPLANAuthoraffiliationCxSpMiddle, div.SIGPLANAuthoraffiliationCxSpMiddle
{mso-style-name:"SIGPLAN Author affiliationCxSpMiddle";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Author name";
mso-style-next:"SIGPLAN Author email";
mso-style-type:export-only;
margin:0in;
margin-bottom:.0001pt;
mso-add-space:auto;
text-align:center;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:9.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANAuthoraffiliationCxSpLast, li.SIGPLANAuthoraffiliationCxSpLast, div.SIGPLANAuthoraffiliationCxSpLast
{mso-style-name:"SIGPLAN Author affiliationCxSpLast";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Author name";
mso-style-next:"SIGPLAN Author email";
mso-style-type:export-only;
margin:0in;
margin-bottom:.0001pt;
mso-add-space:auto;
text-align:center;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:9.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANAuthoremail, li.SIGPLANAuthoremail, div.SIGPLANAuthoremail
{mso-style-name:"SIGPLAN Author email";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Author affiliation";
mso-style-next:"SIGPLAN Basic";
margin-top:2.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
text-align:center;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:8.0pt;
mso-bidi-font-size:9.0pt;
font-family:"Trebuchet MS";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
p.SIGPLANSubtitle, li.SIGPLANSubtitle, div.SIGPLANSubtitle
{mso-style-name:"SIGPLAN Subtitle";
mso-style-unhide:no;
mso-style-next:"SIGPLAN Basic";
margin-top:6.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
text-align:center;
line-height:18.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-hyphenate:none;
font-size:14.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
font-weight:bold;
mso-bidi-font-weight:normal;}
p.SIGPLANParagraphSubparagraphheading, li.SIGPLANParagraphSubparagraphheading, div.SIGPLANParagraphSubparagraphheading
{mso-style-name:"SIGPLAN Paragraph\/Subparagraph heading";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Paragraph 1";
mso-style-next:"SIGPLAN Paragraph";
margin-top:7.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
text-align:justify;
line-height:10.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
mso-outline-level:4;
font-size:9.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
span.SIGPLANParagraphheading
{mso-style-name:"SIGPLAN Paragraph heading";
mso-style-unhide:no;
mso-style-parent:"";
font-weight:bold;
mso-bidi-font-weight:normal;
font-style:italic;
mso-bidi-font-style:normal;}
p.SIGPLANReferencesheading, li.SIGPLANReferencesheading, div.SIGPLANReferencesheading
{mso-style-name:"SIGPLAN References heading";
mso-style-unhide:no;
mso-style-next:"SIGPLAN Reference";
margin-top:6.0pt;
margin-right:0in;
margin-bottom:5.0pt;
margin-left:0in;
text-indent:0in;
line-height:13.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
page-break-after:avoid;
mso-outline-level:1;
mso-list:l2 level1 lfo3;
mso-hyphenate:none;
tab-stops:list 0in;
font-size:11.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";
font-weight:bold;
mso-bidi-font-weight:normal;}
p.SIGPLANReference, li.SIGPLANReference, div.SIGPLANReference
{mso-style-name:"SIGPLAN Reference";
mso-style-unhide:no;
mso-style-parent:"SIGPLAN Paragraph 1";
margin-top:0in;
margin-right:0in;
margin-bottom:4.0pt;
margin-left:17.0pt;
text-align:justify;
text-indent:-17.0pt;
line-height:9.0pt;
mso-line-height-rule:exactly;
mso-pagination:widow-orphan;
font-size:8.0pt;
mso-bidi-font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Times New Roman";}
span.SIGPLANCode
{mso-style-name:"SIGPLAN Code";
mso-style-unhide:no;
mso-style-parent:"";
mso-ansi-font-size:8.0pt;
font-family:"Lucida Console";
mso-ascii-font-family:"Lucida Console";
mso-hansi-font-family:"Lucida Console";}
.MsoChpDefault
{mso-style-type:export-only;
mso-default-props:yes;
font-size:10.0pt;
mso-ansi-font-size:10.0pt;
mso-bidi-font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in .75in 1.0in .75in;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-paper-source:0;}
div.WordSection1
{page:WordSection1;}
@page WordSection2
{size:8.5in 11.0in;
margin:1.0in .75in 1.0in .75in;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-columns:2 even 24.0pt;
mso-paper-source:0;}
div.WordSection2
{page:WordSection2;}
@page WordSection3
{size:8.5in 11.0in;
margin:1.0in .75in 1.0in .75in;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-paper-source:0;}
div.WordSection3
{page:WordSection3;}
/* List Definitions */
@list l0
{mso-list-id:145319201;
mso-list-type:hybrid;
mso-list-template-ids:-545126026 67698689 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:.25in;
text-indent:-.25in;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:.75in;
text-indent:-.25in;
font-family:"Courier New";
mso-bidi-font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:1.25in;
text-indent:-.25in;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:1.75in;
text-indent:-.25in;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:2.25in;
text-indent:-.25in;
font-family:"Courier New";
mso-bidi-font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:2.75in;
text-indent:-.25in;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:3.25in;
text-indent:-.25in;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:3.75in;
text-indent:-.25in;
font-family:"Courier New";
mso-bidi-font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:4.25in;
text-indent:-.25in;
font-family:Wingdings;}
@list l1
{mso-list-id:756485799;
mso-list-template-ids:162827036;}
@list l1:level1
{mso-level-style-link:"SIGPLAN Section heading";
mso-level-suffix:none;
mso-level-text:"%1\. ";
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:0in;
text-indent:0in;}
@list l1:level2
{mso-level-suffix:none;
mso-level-text:"%1\.%2 ";
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:0in;
text-indent:0in;}
@list l1:level3
{mso-level-suffix:none;
mso-level-text:"%1\.%2\.%3 ";
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:.5in;
text-indent:-.5in;}
@list l1:level4
{mso-level-text:"%1\.%2\.%3\.%4";
mso-level-tab-stop:.5in;
mso-level-number-position:left;
margin-left:.5in;
text-indent:-.5in;}
@list l1:level5
{mso-level-text:"%1\.%2\.%3\.%4\.%5";
mso-level-tab-stop:.75in;
mso-level-number-position:left;
margin-left:.75in;
text-indent:-.75in;}
@list l1:level6
{mso-level-text:"%1\.%2\.%3\.%4\.%5\.%6";
mso-level-tab-stop:.75in;
mso-level-number-position:left;
margin-left:.75in;
text-indent:-.75in;}
@list l1:level7
{mso-level-text:"%1\.%2\.%3\.%4\.%5\.%6\.%7";
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
margin-left:1.0in;
text-indent:-1.0in;}
@list l1:level8
{mso-level-text:"%1\.%2\.%3\.%4\.%5\.%6\.%7\.%8";
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
margin-left:1.0in;
text-indent:-1.0in;}
@list l1:level9
{mso-level-text:"%1\.%2\.%3\.%4\.%5\.%6\.%7\.%8\.%9";
mso-level-tab-stop:1.25in;
mso-level-number-position:left;
margin-left:1.25in;
text-indent:-1.25in;}
@list l2
{mso-list-id:1644460410;
mso-list-type:hybrid;
mso-list-template-ids:-377845136 -1784543178 67567641 67567643 67567631 67567641 67567643 67567631 67567641 67567643;}
@list l2:level1
{mso-level-number-format:none;
mso-level-style-link:"SIGPLAN References heading";
mso-level-text:References;
mso-level-tab-stop:0in;
mso-level-number-position:left;
margin-left:0in;
text-indent:0in;}
@list l2:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:1.5in;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:3.0in;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:4.5in;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l3
{mso-list-id:1804500217;
mso-list-type:hybrid;
mso-list-template-ids:1316771182 -1213953032 67567641 67567643 67567631 67567641 67567643 67567631 67567641 67567643;}
@list l3:level1
{mso-level-number-format:none;
mso-level-style-link:"SIGPLAN Abstract heading";
mso-level-text:Abstract;
mso-level-tab-stop:0in;
mso-level-number-position:left;
margin-left:0in;
text-indent:0in;}
@list l3:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l3:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:1.5in;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l3:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l3:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:3.0in;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l3:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l3:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:4.5in;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
-->
</style>
<div class="WordSection1">
<div class="SIGPLANSubtitle">
<span style="font-size: 18.0pt; mso-bidi-font-size: 10.0pt;">Systems
Programming in the Distributed, Multicore World with <i style="mso-bidi-font-style: normal;">Go</i>, <i style="mso-bidi-font-style: normal;">Rust</i>, and <i style="mso-bidi-font-style: normal;">ParaSail</i><span style="mso-spacerun: yes;">
</span></span></div>
<div align="center">
<table border="0" cellpadding="0" cellspacing="0" class="MsoNormalTable" style="border-collapse: collapse; mso-padding-alt: 17.0pt 0in 50.0pt 0in; mso-yfti-tbllook: 480; width: 50%px;">
<tbody>
<tr style="mso-yfti-firstrow: yes; mso-yfti-irow: 0; mso-yfti-lastrow: yes;">
<td style="padding: 17.0pt 0in 50.0pt 0in; width: 100.0%;" valign="top" width="100%">
<div class="SIGPLANAuthorname">
S. Tucker Taft</div>
<div class="SIGPLANAuthoraffiliation">
AdaCore<br />
<i style="mso-bidi-font-style: normal;">24 Muzzey Street, 3<sup>rd</sup> Floor<br />
Lexington, MA<span style="mso-spacerun: yes;"> </span>02421</i></div>
<div class="SIGPLANAuthoremail">
taft@adacore.com</div>
</td>
</tr>
</tbody></table>
</div>
</div>
<span style="font-family: "Times New Roman"; font-size: 12.0pt; mso-ansi-language: EN-US; mso-bidi-font-family: "Times New Roman"; mso-bidi-font-size: 10.0pt; mso-bidi-language: AR-SA; mso-fareast-font-family: "Times New Roman"; mso-fareast-language: EN-US;"><br clear="all" style="mso-break-type: section-break; page-break-before: auto;" />
</span>
<div class="WordSection2">
<div class="SIGPLANAbstractheading" style="margin-left: 0in; mso-list: l3 level1 lfo2; text-indent: 0in;">
<span style="mso-list: Ignore;">Abstract<span style="font: 7.0pt "Times New Roman";">
</span></span> </div>
<div class="SIGPLANParagraphSubparagraphheading">
The distributed, multicore train
is stopping for no programmer, and especially the systems programmer will need
to be ready to hop on to the distributed parallel programming paradigm to keep
their systems running as efficiently as possible on the latest hardware
environments.<span style="mso-spacerun: yes;"> </span>There are three new
systems programming languages that have appeared in the last few years which
are attempting to provide a safe, productive, and efficient parallel programming
capability.<span style="mso-spacerun: yes;"> </span><i style="mso-bidi-font-style: normal;">Go</i> is a new language from Google, <i style="mso-bidi-font-style: normal;">Rust</i> is a new language from Mozilla Research, and <i style="mso-bidi-font-style: normal;">ParaSail</i> is a new language from
AdaCore.<span style="mso-spacerun: yes;"> </span>This talk will describe the
challenges these languages are trying to address, and the various similar and
differing choices that have been made to solve these challenges.</div>
<div class="SIGPLANParagraphSubparagraphheading">
<span class="SIGPLANParagraphheading">Keywords </span>multicore, distributed, parallel
programming, systems programming language, Go language, Rust language, ParaSail
language</div>
<div class="SIGPLANParagraph">
<br /></div>
<div class="SIGPLANSectionheading" style="margin-left: 0in; mso-list: l1 level1 lfo1; text-indent: 0in;">
<span style="mso-no-proof: yes;"><span style="mso-list: Ignore;">1. </span></span><span style="mso-no-proof: yes;">Introduction</span></div>
<div class="SIGPLANSectionheading" style="line-height: normal; mso-list: none; text-align: justify;">
<span style="font-size: 9.0pt; font-weight: normal; mso-bidi-font-size: 10.0pt;">The distributed, multicore train is stopping for no
programmer, and especially the systems programmer will need to be ready to hop
on to the distributed parallel programming paradigm to keep their systems
running as efficiently as possible on the latest hardware environments.<span style="mso-spacerun: yes;"> </span>There are three new systems programming
languages that have appeared in the last few years which are attempting to
provide a safe, productive, and efficient parallel programming capability.<span style="mso-spacerun: yes;"> </span><i style="mso-bidi-font-style: normal;">Go</i>
is a new language from Google [1], <i style="mso-bidi-font-style: normal;">Rust</i>
is a new language from Mozilla [2], and <i style="mso-bidi-font-style: normal;">ParaSail</i>
is a new language from AdaCore [3][4].</span></div>
<div class="SIGPLANSectionheading" style="line-height: normal; mso-list: none; text-align: justify;">
<span style="font-size: 9.0pt; font-weight: normal; mso-bidi-font-size: 10.0pt;">The designers of <i style="mso-bidi-font-style: normal;">Go</i>,
<i style="mso-bidi-font-style: normal;">Rust</i>, and <i style="mso-bidi-font-style: normal;">ParaSail</i> all are facing a common challenge -- how to help
programmers address the new distributed and multicore architectures, without
having the complexity of programming going past that which is manageable by the
professional, yet still human, programmer.<span style="mso-spacerun: yes;">
</span>All programming languages evolve, and as a rule, they tend to get more
complex, not less so.<span style="mso-spacerun: yes;"> </span>If every time a
new hardware architecture becomes important, the programming language is
enhanced to provide better support for that architecture, the language can
become totally unwieldy, even for the best programmers.<span style="mso-spacerun: yes;"> </span>When the architectures changes radically, as
with the new massively distributed and/or multicore/manycore architectures, this
may mean that the language no longer hangs together at all, and instead has
become a federation of sublanguages, much like a house that has been added onto
repeatedly with a different style for each addition.</span></div>
<div class="SIGPLANSectionheading" style="line-height: normal; mso-list: none; text-align: justify;">
<span style="font-size: 9.0pt; font-weight: normal; mso-bidi-font-size: 10.0pt;">Because of the complexity curse associated with language
evolution, when there is a significant shift in the hardware landscape, there
is a strong temptation to start over in programming language design.<span style="mso-spacerun: yes;"> </span>After many years of a relatively stable
programming language world, we now see a new burst of activity on the language
design front, inspired in large part by the sense that our existing mainstream
languages are either not going to be supportive enough, or that they are
becoming simply too complex in trying to support both the old and new hardware
paradigms through a series of language extensions.</span></div>
<div class="SIGPLANSectionheading" style="margin-left: 0in; mso-list: l1 level1 lfo1; text-align: justify; text-indent: 0in;">
<span style="mso-list: Ignore;">2. </span>Go from Google</div>
<div class="SIGPLANSectionheading" style="line-height: normal; mso-list: none; text-align: justify;">
<i style="mso-bidi-font-style: normal;"><span style="font-size: 9.0pt; font-weight: normal; mso-bidi-font-size: 10.0pt;">Go</span></i><span style="font-size: 9.0pt; font-weight: normal; mso-bidi-font-size: 10.0pt;">, <i style="mso-bidi-font-style: normal;">Rust</i>, and <i style="mso-bidi-font-style: normal;">ParaSail</i> all emerged over the past few years, each with its own
approach to managing complexity while supporting parallelism.<span style="mso-spacerun: yes;"> </span><i style="mso-bidi-font-style: normal;">Go</i>
from Google is the brain child of Rob Pike and his colleagues at Google.<span style="mso-spacerun: yes;"> </span>Rob was at Bell Labs in the early Unix and C
days, and in many ways Go inherits the C tradition of simplicity and power.
Unlike C, storage management has been taken over by the Go run-time through a
general purpose garbage collection approach, but like C, care is still needed
in other areas to ensure overall program safety.<span style="mso-spacerun: yes;"> </span></span></div>
<div class="SIGPLANSectionheading" style="line-height: normal; mso-list: none; text-align: justify;">
<span style="font-size: 9.0pt; font-weight: normal; mso-bidi-font-size: 10.0pt;">From the multicore perspective, <i style="mso-bidi-font-style: normal;">Go</i> uses <i style="mso-bidi-font-style: normal;">goroutines</i> for
structuring large computations into a set of smaller potentially parallel
computations.<span style="mso-spacerun: yes;"> </span>Goroutines are easy to
create – essentially any stand-alone call on a function or a method can be
turned into a goroutine by simply prefixing it with the word “</span><span style="font-family: Courier; font-size: 9.0pt; font-weight: normal; mso-bidi-font-size: 10.0pt;">go</span><span style="font-size: 9.0pt; font-weight: normal; mso-bidi-font-size: 10.0pt;">.”<span style="mso-spacerun: yes;"> </span>Once a
goroutine is spawned, it executes independently of the rest of the code.<span style="mso-spacerun: yes;"> </span>A goroutine is allowed to outlive the
function that spawns it, thanks to the support of the garbage collector; local
variables of the spawning function will live as long as necessary if they are
visible to the spawned goroutine.</span></div>
<div class="SIGPLANParagraph1">
For goroutines to be useful, they need to
communicate their results back to the spawning routine.<span style="mso-spacerun: yes;"> </span>This is generally done using strongly-typed <i style="mso-bidi-font-style: normal;">channels </i>in Go.<span style="mso-spacerun: yes;"> </span>A channel can be passed as a parameter as
part of spawning a goroutine, and then as the goroutine performs its
computation it can <i style="mso-bidi-font-style: normal;">send</i> one or more
results into the channel.<span style="mso-spacerun: yes;"> </span>Meanwhile, at
some appropriate point after spawning the goroutine, the spawner can attempt to
<i style="mso-bidi-font-style: normal;">receive</i> one or more values from the
channel.<span style="mso-spacerun: yes;"> </span>A channel can be unbuffered,
providing a synchronous communication between sender and receiver, or it can
provide a <i style="mso-bidi-font-style: normal;">buffer </i>of a specified size,
effectively creating a message queue.<span style="mso-spacerun: yes;"> </span></div>
<div class="SIGPLANParagraph1">
<br /></div>
<div class="SIGPLANParagraph1">
Communication between goroutines can also go
directly through shared global variables.<span style="mso-spacerun: yes;">
</span>However, some sort of synchronization through channels or explicit locks
is required to ensure that the shared variables are updated and read in an
appropriate sequence. </div>
<div class="SIGPLANParagraph1">
<br /></div>
<div class="SIGPLANParagraph1">
Here is an example Go program that counts the number
of words in a string, presuming they are separated by one or more <i style="mso-bidi-font-style: normal;">separator</i> characters, dividing
multi-character strings in half and passing them off to <i style="mso-bidi-font-style: normal;">goroutines</i> for recursive word counts:</div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>func Word_Count</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>(s string; separators string) int = {</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>const slen = len(s)</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>switch slen {</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>case 0: return 0 // Empty string</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>case 1:<span style="mso-spacerun: yes;">
</span><span style="mso-spacerun: yes;"> </span>// single-char string</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;">
</span>if strings.ContainsRune</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>(separators, S[0]) {</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>return 0<span style="mso-spacerun: yes;"> </span>// A single separator</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>} else {</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>return 1<span style="mso-spacerun: yes;"> </span>// A single non-separator</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>}</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>default:<span style="mso-spacerun: yes;"> </span>// divide string and recurse</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;">
</span>const half_len = slen/2</span></span><span style="font-family: "Lucida Console"; font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;">
</span>// Create two chans and two goroutines</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>var left_sum = make(chan int)<span style="mso-spacerun: yes;"> </span></span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>var right_sum = make(chan int)</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>go func(){left_sum <- span="" word_count=""></-></span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>(s[0..half_len], separators)}()</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;"> </span>go func() {right_sum <- span="" word_count=""></-></span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>(s[half_len..slen],
separators)}()</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;">
</span>// Read partial sums</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>// and adjust total if word was
divided</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>if strings.ContainsRune</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>(separators, s[half_len-1]) ||</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;"> </span>strings.ContainsRune</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>(separators, s[half_len]) {</span></span><span style="font-family: "Lucida Console"; font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;">
</span>// No adjustment needed</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>return <-left_sum right_sum="" span=""></-left_sum></span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>} else {// Minus 1 because word
divided</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>return <-left_sum -="" 1="" right_sum="" span=""></-left_sum></span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>}</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>}</span></span></div>
<div align="left" class="SIGPLANParagraph1" style="line-height: normal; text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>}</span></span></div>
<div class="SIGPLANSubsectionheading" style="margin-left: 0in; mso-list: l1 level2 lfo1; tab-stops: .5in; text-indent: 0in;">
<span style="mso-list: Ignore;">2.1 </span>Unique Features of Go</div>
<div class="SIGPLANParagraph1">
Go has some unusual features.<span style="mso-spacerun: yes;"> </span>Whether a declaration is <i style="mso-bidi-font-style: normal;">exported </i>is determined by whether or not its name begins with an
upper-case letter (as defined by Unicode); if the declaration is a package-level
declaration or is the declaration of a field or a method, then if the name
starts with an upper-case letter, the declaration is visible outside the
current package.</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Every Go source file begins
with a specification of the <i style="mso-bidi-font-style: normal;">package</i>
it is defining (possibly only in part).<span style="mso-spacerun: yes;"> </span>One
source file may <i style="mso-bidi-font-style: normal;">import</i> declarations
from another by specifying the path to the file that contains the declarations,
but within the importing code the exported declarations of the imported code
are referenced using the imported file’s <i style="mso-bidi-font-style: normal;">package</i>
name, which need not match that of the imported file’s filename.<span style="mso-spacerun: yes;"> </span>Of course projects would typically establish
standard naming conventions which would align source file names and package
names somehow.</div>
<div class="SIGPLANParagraph1">
<br /></div>
<div class="SIGPLANParagraph1">
Go provides a <i style="mso-bidi-font-style: normal;">reflection</i>
capability, which is used, for example, to convert an object of an arbitrary
type into a human-readable representation.<span style="mso-spacerun: yes;">
</span>The “<span style="font-family: Courier;">%v</span>” format in Go’s version
of <i style="mso-bidi-font-style: normal;">printf</i> does this, allowing
arbitrarily complex structs to be written out with something as simple as:</div>
<div class="SIGPLANParagraph">
<br /></div>
<div class="SIGPLANParagraph">
<span style="font-family: Courier;">fmt.Printf(“%v”,
my_complex_object)</span></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Printf is implemented in Go
itself, using the “<span style="font-family: Courier;">reflect</span>” package.</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
There are no uninitialized
variables in Go.<span style="mso-spacerun: yes;"> </span>If a variable is not
explicitly initialized when declared, it is initialized by default to the <i style="mso-bidi-font-style: normal;">zero </i>of its type, where each type has an
appropriately-defined <i style="mso-bidi-font-style: normal;">zero</i>, typically
either the zero numeric value or the <span style="font-family: Courier;">nil</span>
(aka “null”) pointer value, or some composite object with all components having
their appropriate zero value.</div>
<div class="SIGPLANSubsectionheading" style="margin-left: 0in; mso-list: l1 level2 lfo1; tab-stops: .5in; text-indent: 0in;">
<span style="mso-list: Ignore;">2.2 </span>What Go Leaves Out</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Because complexity was a
major concern during all three of these language designs, some of the most
important design decisions were about what to leave <i style="mso-bidi-font-style: normal;">out</i> of the language.<span style="mso-spacerun: yes;"> </span>Here we
mention some of the features that Go does <i style="mso-bidi-font-style: normal;">not
</i>have.</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Go does not permit direct cyclic
dependencies between packages.<span style="mso-spacerun: yes;"> </span>However,
the Go <i style="mso-bidi-font-style: normal;">interface</i> capability permits
the construction of<span style="mso-spacerun: yes;"> </span>recursive control or
data structures that cross packages, because an interface declared in one
package can be implemented by a type declared in another package without either
package being directly dependent on the other.</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Like C, Go has no generic
template facility.<span style="mso-spacerun: yes;"> </span>There are some builtin
type constructors, such as <span style="font-family: Courier;">array</span>, <span style="font-family: Courier;">map</span>, and <span style="font-family: Courier;">chan</span>,
which are effectively parameterized type constructors, but there is no way for
the user to create their own such type constructor.<span style="mso-spacerun: yes;"> </span>Unlike C, there is no macro facility which
might be used to create something like a parameterized type.<span style="mso-spacerun: yes;"> </span>Nevertheless, Go’s flexible <i style="mso-bidi-font-style: normal;">interface</i> and <i style="mso-bidi-font-style: normal;">reflection</i> capabilities allow the creation of complex data
structures that depend only on the presence of a user-provided method such as <span style="font-family: Courier;">Hash</span> and the <span style="font-family: Courier;">DeepEqual</span>
function of the <span style="font-family: Courier;">reflect</span> package.</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Go does not allow
user-defined operators.<span style="mso-spacerun: yes;"> </span>Various
operators are built in for the built-in types, such as <span style="font-family: Courier;">int</span> and <span style="font-family: Courier;">float32</span>.<span style="mso-spacerun: yes;"> </span>Interestingly enough, Go does include
built-in complex types (<span style="font-family: Courier;">complex64</span> and <span style="font-family: Courier;">complex128</span>) with appropriate operators.</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Go does not have
exceptions.<span style="mso-spacerun: yes;"> </span>However, functions and
methods<span style="mso-spacerun: yes;"> </span>may return multiple results, and
often errors are represented by having a second return value called <span style="font-family: Courier;">error</span> that is non-nil on error.<span style="mso-spacerun: yes;"> </span>Unlike in C, you cannot ignore such an extra
parameter; unless you explicitly assign it to an object of name “_”.<span style="mso-spacerun: yes;"> </span>When things go really wrong in Go, a run-time
<i style="mso-bidi-font-style: normal;">panic</i> ensues, and presumably during
development, you are tossed into a debugger.</div>
<div class="SIGPLANSectionheading" style="margin-left: 0in; mso-list: l1 level1 lfo1; text-indent: 0in;">
<span style="mso-list: Ignore;">3. </span><span style="mso-no-proof: yes;">Rust from Mozilla Research</span></div>
<div class="SIGPLANParagraph1">
The modern web browser represents one of the most
complex and critical pieces of software of the internet era.<span style="mso-spacerun: yes;"> </span>The browser is also a place where performance
is critical, and there are many opportunities for using parallelism as a web
page is “rendered.”<span style="mso-spacerun: yes;"> </span>The <i style="mso-bidi-font-style: normal;">Rust</i> language arose originally as a
personal project by one of the engineers at Mozilla Research (Graydon Hoare), and
has grown now into a Mozilla-sponsored research effort.<span style="mso-spacerun: yes;"> </span>Rust has been designed to help address the
complexity of building components of a modern browser-centric software
infrastructure, in the context of the new distributed multicore hardware
environment.</div>
<div class="SIGPLANParagraph">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Like Go, Rust has chosen to
simplify storage management by building garbage collection into the
language.<span style="mso-spacerun: yes;"> </span>Unlike Go, Rust has chosen to
restrict garbage collection to per-task heaps, and adopt a <i style="mso-bidi-font-style: normal;">unique</i> <i style="mso-bidi-font-style: normal;">ownership</i> policy
for data that can be exchanged between tasks.<span style="mso-spacerun: yes;">
</span>What this means is that data that can be shared between tasks is visible
to only one of them at a time, and only through a single pointer at a time
(hence an <i style="mso-bidi-font-style: normal;">owning </i>pointer).<span style="mso-spacerun: yes;"> </span>This eliminates the possibility of data races
between tasks, and eliminates the need for a garbage collector for this global
data exchange heap.<span style="mso-spacerun: yes;"> </span>When an owning
pointer is discarded, the storage designated by the pointer may be immediately
reclaimed – so no garbage accumulates in the global exchange heap.</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Here is a Rust version of the
Word Count program, recursing on multi-character strings with subtasks
encapsulated as <i style="mso-bidi-font-style: normal;">futures</i> computing the
subtotals of each string slice:</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;">fn Word_Count</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>(S :
&str; Separators : &str) -> uint {</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>let Len =
S.len();</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>match Len
{</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;"> </span>0 => return 0; // Empty string</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>1 =>
return <span style="mso-spacerun: yes;"> </span>// one-char string</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>if
Separators.contains(S[0]) { 0 } </span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>else
{ 1 };<span style="mso-spacerun: yes;"> </span>// 0 or 1 words</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>_
=><span style="mso-spacerun: yes;"> </span>// Divide and recurse</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>let
Half_Len = Len/2;</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>let
Left_Sum = future::spawn {</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>||
Word_Count(S.slice</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;">
</span>(0, Half_Len-1), Separators)};</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>let
Right_Sum = future::spawn {</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>||
Word_Count(S.slice</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;">
</span>(Half_Len, Len-1), Separators)};</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;">
</span>// Adjust sum if a word is divided</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>if
Separators.contains(S[Half_Len]) ||</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;">
</span>Separators.contains(S[Half_Len+1]) { </span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>//
No adjustment needed</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;">
</span>return </span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>Left_Sum.get()
+ Right_Sum.get();<span style="mso-spacerun: yes;"> </span></span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;"> </span>} else { </span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>//
Subtract one because word divided</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;">
</span>return </span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;">
</span>Left_Sum.get()+Right_Sum.get() – 1; </span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>}</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>}</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>}</span></span></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Rust does not have special syntax
for spawning a “task” (Rust’s equivalent of a “goroutine”) nor declaring the
equivalent of a “channel,” but instead relies on its <i style="mso-bidi-font-style: normal;">generic template</i> facility and a run-time library of<span style="mso-spacerun: yes;"> </span>threading and synchronization
capabilities.<span style="mso-spacerun: yes;"> </span>In the above example, we
illustrate the use of <i style="mso-bidi-font-style: normal;">futures</i> which
are essentially a combination of a task and an unbuffered channel used to
capture the result of a computation.<span style="mso-spacerun: yes;">
</span>There are several other mechanisms for spawning and coordinating tasks,
but they all depend on the basic tasking model, as mentioned above, where each
task has its own garbage-collected heap for task-local computation (manipulated
by what Rust calls <i style="mso-bidi-font-style: normal;">managed</i> pointers),
plus access via <i style="mso-bidi-font-style: normal;">owning</i> pointers to
data that can be shared between tasks (by sending an owning pointer in a
message).</div>
<div class="SIGPLANSubsectionheading" style="margin-left: 0in; mso-list: l1 level2 lfo1; tab-stops: .5in; text-indent: 0in;">
<span style="mso-list: Ignore;">3.1 </span>Rust Memory Management Performance</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
One of the major advantages
of the <i style="mso-bidi-font-style: normal;">Rust</i> approach to memory
management is that garbage collection is local to a single task.<span style="mso-spacerun: yes;"> </span>By contrast, in <i style="mso-bidi-font-style: normal;">Go</i> each garbage collector thread has to operate on data that is potentially
visible to <i style="mso-bidi-font-style: normal;">all</i> goroutines, requiring
a garbage collection algorithm that synchronizes properly with all of the
active goroutines, as well as with any other concurrent garbage collector
threads (presuming garbage collection itself needs to take advantage of
parallel processing to keep up with multithreaded garbage generation).<span style="mso-spacerun: yes;"> </span></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
In Rust, a conventional <i style="mso-bidi-font-style: normal;">single-threaded</i> garbage collector algorithm
is adequate, because any given garbage collector is working on a single
per-task heap.<span style="mso-spacerun: yes;"> </span>Furthermore, storage
visible via owning pointers needs no garbage collection at all, as releasing an
owning pointer means that the associated storage can also be released
immediately.</div>
<div class="SIGPLANSubsectionheading" style="margin-left: 0in; mso-list: l1 level2 lfo1; tab-stops: .5in; text-indent: 0in;">
<span style="mso-list: Ignore;">3.2 </span>The Costs of Safety and
Performance</div>
<div class="SIGPLANParagraph1">
One of the downsides of added safety and performance
can be added complexity.<span style="mso-spacerun: yes;"> </span>As we see, Rust
has added safety by allowing access to sharable data only via pointers that
give exclusive access to one task at a time, and added performance because
garbage collection is single-threaded.<span style="mso-spacerun: yes;">
</span>However, as a result, Rust needs several kinds of pointers.<span style="mso-spacerun: yes;"> </span>In fact, there are four kinds of pointers in
Rust, <i style="mso-bidi-font-style: normal;">managed</i> pointers (identified by
‘@’as a prefix on a type) for per-task garbage-collected storage, <i style="mso-bidi-font-style: normal;">owning</i> pointers (identified by ‘~’) for
data that is sharable between tasks, <i style="mso-bidi-font-style: normal;">borrowed</i>
pointers (identified by ‘&’) that can temporarily refer to either per-task
or sharable data, and <i style="mso-bidi-font-style: normal;">raw</i> pointers
(identified by ‘*’), analogous to typical C pointers, with no guarantees of
safety.</div>
<div class="SIGPLANSectionheading" style="margin-left: 0in; mso-list: l1 level1 lfo1; text-indent: 0in;">
<span style="mso-list: Ignore;">4. </span>ParaSail
from AdaCore</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
The <i style="mso-bidi-font-style: normal;">ParaSail</i> language from AdaCore takes support for parallelism one
step further than Go or Rust, by treating <i style="mso-bidi-font-style: normal;">all</i>
expression evaluation in the language as <i style="mso-bidi-font-style: normal;">implicitly</i>
parallel, while also embracing full type and data-race safety.<span style="mso-spacerun: yes;"> </span>Rather than adding complexity to accomplish
this, the explicit goal for ParaSail was to achieve safety and pervasive
parallelism by <i style="mso-bidi-font-style: normal;">simplifying</i> the language,
eliminating impediments to parallelism by eliminating many of the features that
make safe, implicit parallelism harder.</div>
<div class="SIGPLANSubsectionheading" style="margin-left: 0in; mso-list: l1 level2 lfo1; tab-stops: .5in; text-indent: 0in;">
<span style="mso-list: Ignore;">4.1 </span>What ParaSail Leaves Out</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Some of the features left <i style="mso-bidi-font-style: normal;">out</i> of ParaSail include the following:</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="margin-left: .25in; mso-list: l0 level1 lfo4; text-indent: -.25in;">
<span style="font-family: Symbol; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;">·<span style="font: 7.0pt "Times New Roman";">
</span></span></span>No pointers</div>
<div class="SIGPLANParagraph" style="margin-left: .25in; mso-list: l0 level1 lfo4; text-indent: -.25in;">
<span style="font-family: Symbol; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;">·<span style="font: 7.0pt "Times New Roman";">
</span></span></span>No global variables</div>
<div class="SIGPLANParagraph" style="margin-left: .25in; mso-list: l0 level1 lfo4; text-indent: -.25in;">
<span style="font-family: Symbol; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;">·<span style="font: 7.0pt "Times New Roman";">
</span></span></span>No run-time exception handling</div>
<div class="SIGPLANParagraph" style="margin-left: .25in; mso-list: l0 level1 lfo4; text-indent: -.25in;">
<span style="font-family: Symbol; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;">·<span style="font: 7.0pt "Times New Roman";">
</span></span></span>No explicit threads, no explicit locking nor
signaling</div>
<div class="SIGPLANParagraph" style="margin-left: .25in; mso-list: l0 level1 lfo4; text-indent: -.25in;">
<span style="font-family: Symbol; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;">·<span style="font: 7.0pt "Times New Roman";">
</span></span></span>No explicit heap, no garbage collection needed</div>
<div class="SIGPLANParagraph" style="margin-left: .25in; mso-list: l0 level1 lfo4; text-indent: -.25in;">
<span style="font-family: Symbol; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;">·<span style="font: 7.0pt "Times New Roman";">
</span></span></span>No parameter aliasing</div>
<div class="SIGPLANParagraph" style="margin-left: .25in; text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
So what is left?<span style="mso-spacerun: yes;"> </span>ParaSail provides a familiar
class-and-interface-based object-oriented programming model, with mutable
objects and assignment statements.<span style="mso-spacerun: yes;"> </span>But
ParaSail also supports a highly functional style of programming, aided by the
lack of global variables, where the only variable data visible to a function is
via parameters explicitly specified as <b style="mso-bidi-font-weight: normal;">var</b>
parameters.<span style="mso-spacerun: yes;"> </span>This means that the
side-effects of a function are fully captured by its parameter profile, which
together with the lack of parameter aliasing allows the compiler to verify
easily whether two computations can safely be performed in parallel.</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
By design, every expression
in ParaSail can be evaluated in parallel.<span style="mso-spacerun: yes;">
</span>If two parts of the same expression might conflict, the expression is
not a legal ParaSail expression.<span style="mso-spacerun: yes;"> </span>The net
effect is that the compiler can choose where and when to insert parallelism
strictly based on what makes the most sense from a performance point of view. <span style="mso-spacerun: yes;"> </span>Here, for example, is the Word Count example
in ParaSail, where parallelism is implicit in the recursive calls on Word Count,
without any explicit action by the programmer:</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;">func
Word_Count</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>(S : Univ_String; </span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>Separators : </span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>Countable_Set<univ_character> :=
[' '])</univ_character></span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>-> Univ_Integer is</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>case |S| of</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>[0] => return 0<span style="mso-spacerun: yes;"> </span>// Empty string</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>[1] =></span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>if S[1] in Separators then</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>return 0<span style="mso-spacerun: yes;"> </span>// No words</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>else</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>return 1<span style="mso-spacerun: yes;"> </span>// One word</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>end if</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>[..] =><span style="mso-spacerun: yes;"> </span>// Divide and recurse</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>const Half_Len := |S|/2</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>const Sum := Word_Count</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>(S[1 .. Half_Len], Separators) +</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>Word_Count</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;">
</span>(S[Half_Len <.. |S|], Separators)</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>if S[Half_Len] in Separators or else </span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>S[Half_Len+1] in Separators then</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>return Sum <span style="mso-spacerun: yes;"> </span>// No adjustment needed</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>else</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>return Sum-1<span style="mso-spacerun: yes;"> </span>// Adjust sum</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>end if</span></span></div>
<div align="left" class="SIGPLANParagraph" style="text-align: left;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;"><span style="mso-spacerun: yes;"> </span>end case</span></span></div>
<div align="left" class="SIGPLANParagraph" style="line-height: normal; text-align: left; text-indent: 0in;">
<span class="SIGPLANCode"><span style="font-size: 8.0pt; mso-bidi-font-size: 10.0pt;">end func Word_Count </span></span></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Although there is no explicit
use of a parallel construct, the sum of the two recursive calls on Word_Count
can be evaluated in parallel, with the compiler automatically creating a <i style="mso-bidi-font-style: normal;">picothread</i> for each recursive call,
waiting for their completion, and then summing the results, without the
programmer having to add explicit directives.</div>
<div class="SIGPLANSubsectionheading" style="margin-left: 0in; mso-list: l1 level2 lfo1; tab-stops: .5in; text-indent: 0in;">
<span style="mso-list: Ignore;">4.2 </span>Implicit and Explicit Parallelism
in ParaSail</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Explicit parallelism may be
specified if desired in ParaSail, or the programmer can simply rely on the
compiler to insert it where it makes the most sense.<span style="mso-spacerun: yes;"> </span>The general philosophy is that the semantics
are parallel by default, and the programmer needs to work a bit harder if they
want to force sequential semantics.<span style="mso-spacerun: yes;"> </span>For
example, statements in ParaSail can be separated as usual with “<span style="font-family: Courier;">;</span>” (which is implicit at the end of the line
when appropriate), or by “<span style="font-family: Courier;">||</span>” if the
programmer wants to request explicit parallelism, or by “<span style="font-family: Courier;">then</span>” if the programmer wants to disallow
implicit parallelism.<span style="mso-spacerun: yes;"> </span>By default the
compiler will evaluate two statements in parallel if there are no data
dependences between them.<span style="mso-spacerun: yes;"> </span></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
As another example of
ParaSail’s implicit and explicit parallelism, the iterations of “<span style="font-family: Courier;">for I in 1..10 loop</span>” are by default executed
in any order, including parallel if there are no data dependences between the
loop iterations, while “<span style="font-family: Courier;">for I in 1..10
forward loop</span>” or “<span style="font-family: Courier;">for I in 1..10
reverse loop</span>” may be specified to prevent parallel evaluation, and “<span style="font-family: Courier;">for I in 1..10 concurrent loop</span>” may be used
to specify that parallel evaluation is desired, and it is an error if there are
any data dependences between the iterations.<span style="mso-spacerun: yes;">
</span>In all these cases, the compiler will ensure that any parallel
evaluation is safe and data-race free, and will complain if there are potential
race conditions when parallel evaluation semantics are specified.</div>
<div class="SIGPLANSubsectionheading" style="margin-left: 0in; mso-list: l1 level2 lfo1; tab-stops: .5in; text-indent: 0in;">
<span style="mso-list: Ignore;">4.3 </span>Simplicity breeds Simplicity in
ParaSail</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
There is somewhat of a <i style="mso-bidi-font-style: normal;">virtuous cycle</i> that occurs when a programming
language is simplified, in that one simplification can lead to another.<span style="mso-spacerun: yes;"> </span>By eliminating pointers and a global heap
from ParaSail, the language can provide fully automatic storage management
without the need for a garbage collector.<span style="mso-spacerun: yes;">
</span>Objects in ParaSail have <i style="mso-bidi-font-style: normal;">value
semantics</i> meaning that assignment copies the value of the right-hand side
into the left-hand side, with no sharing of data.<span style="mso-spacerun: yes;"> </span>A built-in <i style="mso-bidi-font-style: normal;">move</i> operation is provided for moving the value of the right-hand
side into the left-hand side, along with a <i style="mso-bidi-font-style: normal;">swap</i>
for swapping values, thereby reducing the cost of copying while still
preserving <i style="mso-bidi-font-style: normal;">value</i> semantics.</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
Every type in ParaSail has an
extra value, called <i style="mso-bidi-font-style: normal;">null</i>, which is
used to represent an empty or otherwise uninitialized value.<span style="mso-spacerun: yes;"> </span>An object or component may have a <i style="mso-bidi-font-style: normal;">null</i> value of its type T only if it is
declared to be “<span style="font-family: Courier;">optional T</span>”.<span style="mso-spacerun: yes;"> </span>Optional components may be used to implement
trees and linked lists, without the use of explicit pointers, and without the
potential sharing issues associated with pointers, even if behind the scenes
the compiler uses pointers to implement optional objects or components.<span style="mso-spacerun: yes;"> </span>The availability of optional components
effectively allows an object to <i style="mso-bidi-font-style: normal;">grow</i>
and <i style="mso-bidi-font-style: normal;">shrink</i>, meaning that dynamic
structures like hash tables, and higher level notions such as maps and sets,
can be implemented in ParaSail without any explicit pointers, with the
advantages of purely value semantics.</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
The lack of explicit pointers
means that all objects in ParaSail effectively live on the <i style="mso-bidi-font-style: normal;">stack</i>, even though they may still grow and shrink.<span style="mso-spacerun: yes;"> </span>Each scope has its own <i style="mso-bidi-font-style: normal;">region</i>, effectively a local heap that expands and contracts to hold
the objects associated with the scope.<span style="mso-spacerun: yes;">
</span>No garbage collector is needed because when an object goes out of scope,
or an object or one of its component is set back to <i style="mso-bidi-font-style: normal;">null,</i> the associated storage may be immediately reclaimed, much
like storage designated by <i style="mso-bidi-font-style: normal;">owning</i>
pointers in Rust.<span style="mso-spacerun: yes;"> </span>By simplifying the
type model, the storage management in ParaSail is dramatically simpler and of
higher performance, with no complex parallel garbage collection algorithm
required.</div>
<div class="SIGPLANSectionheading" style="margin-left: 0in; mso-list: l1 level1 lfo1; text-indent: 0in;">
<span style="mso-list: Ignore;">5. </span>Implementation
Status and Conclusions</div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
The programming language
design world has been rejuvenated by the new challenges of distributed and
multicore architectures.<span style="mso-spacerun: yes;"> </span>Three new
programming languages designed for building industrial-strength systems have
emerged, <i style="mso-bidi-font-style: normal;">Go</i>, <i style="mso-bidi-font-style: normal;">Rust</i>, and <i style="mso-bidi-font-style: normal;">ParaSail</i>.<span style="mso-spacerun: yes;"> </span>Each of these languages tries to make
parallel programming simpler and safer, while still providing the level of
power and performance needed for the most critical systems development
tasks.<span style="mso-spacerun: yes;"> </span></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
<br /></div>
<div class="SIGPLANParagraph" style="text-indent: 0in;">
From an implementation status
point of view, Go is the most stable of these three new languages, with two compilers
available, and a number of systems built with Go now being deployed.<span style="mso-spacerun: yes;"> </span>Rust and ParaSail are still under
development, but both are available for trial use, with Rust having early on
achieved the compiler <i style="mso-bidi-font-style: normal;">boot strap </i>milestone,
where the Rust compiler is itself implemented in Rust.<span style="mso-spacerun: yes;"> </span>All three languages provide opportunities for
the professional programmer to expand their horizons, and see what sort of new
paradigms and idioms will become more important as we leave behind the era of
simple sequential processing, and enter the era of massively parallel, widely
distributed computing.</div>
<div class="SIGPLANReferencesheading" style="margin-left: 0in; mso-list: l2 level1 lfo3; text-indent: 0in;">
<span style="mso-list: Ignore;">References<span style="font: 7.0pt "Times New Roman";"> </span></span> </div>
<div align="left" class="SIGPLANReference" style="text-align: left;">
[<a href="http://www.blogger.com/null" name="_SIGPLAN_Bibref_unk00"></a><span style="mso-bookmark: _SIGPLAN_Bibref_unk00;"><span style="mso-no-proof: yes;">1</span></span><span style="mso-bookmark: _SIGPLAN_Bibref_unk00;"></span>]<span style="mso-tab-count: 1;"> </span><i style="mso-bidi-font-style: normal;">The Go
Programming Language</i>, Google Corporation, <a href="http://golang.org/">http://golang.org</a></div>
<div align="left" class="SIGPLANReference" style="text-align: left;">
[2]<span style="mso-tab-count: 1;"> </span><i style="mso-bidi-font-style: normal;">The
Rust Programming Language</i>, Mozilla Research, <a href="http://www.rust-lang.org/">http://www.rust-lang.org</a></div>
<div align="left" class="SIGPLANReference" style="text-align: left;">
[3]<span style="mso-tab-count: 1;"> </span><i style="mso-bidi-font-style: normal;">ParaSail:
Less is More with Multicore</i>, S. Tucker Taft, <a href="http://www.embedded.com/design/other/4375616/ParaSail--Less-is-more-with-multicore">http://www.embedded.com/design/other/4375616/ParaSail--Less-is-more-with-multicore</a>
(retrieved 4/1/2013).</div>
<div align="left" class="SIGPLANReference" style="text-align: left;">
[4]<span style="mso-tab-count: 1;"> </span><i style="mso-bidi-font-style: normal;">Designing
ParaSail: A New Programming Language</i>, S. Tucker Taft, http://parasail-programming-language.blogspot.com</div>
</div>
<span style="font-family: "Times New Roman"; font-size: 8.0pt; mso-ansi-language: EN-US; mso-bidi-font-family: "Times New Roman"; mso-bidi-font-size: 10.0pt; mso-bidi-language: AR-SA; mso-fareast-font-family: "Times New Roman"; mso-fareast-language: EN-US;"><br clear="all" style="mso-break-type: section-break; page-break-before: auto;" />
</span>
<div class="SIGPLANBasic">
<br /></div>
<span style="font-family: "Times New Roman"; font-size: 8.0pt; mso-ansi-language: EN-US; mso-bidi-font-family: "Times New Roman"; mso-bidi-font-size: 10.0pt; mso-bidi-language: AR-SA; mso-fareast-font-family: "Times New Roman"; mso-fareast-language: EN-US;"><br clear="all" style="mso-break-type: section-break; page-break-before: auto;" />
</span>
<br />
<div class="SIGPLANBasic">
<br /></div>
Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com13tag:blogger.com,1999:blog-8383004232931899216.post-55397162019706327582013-02-17T17:22:00.000-05:002013-03-09T11:40:41.541-05:00ParaSailing without a (garbage) chuteHere is a video of a presentation on <b>ParaSail</b> given at Mozilla Research in Mountain View, CA a couple of weeks ago, to the folks who are developing the <b>Rust</b> language:<br />
<br />
<a href="https://air.mozilla.org/region-based-storage-management-parasailing-without-a-garbage-chute/" target="_blank">https://air.<span class="il">mozilla</span>.org/<wbr></wbr>region-based-storage-<wbr></wbr>management-parasailing-<wbr></wbr>without-a-garbage-chute/</a><br />
<br />
A particular area of interest was the use of pointer-free <i>region-based storage management</i> which eliminates the need for a garbage collector. Rust has <i>per-task heaps</i> which are garbage collected, but in a single-threaded environment, plus a <i>global heap</i> which is managed more like one of ParaSail's regions, where all pointers into the global heap are <i>unique/owned</i> pointers. Setting such a pointer to null allows immediate reclamation of the associated storage, preventing accumulation of any garbage.<br />
<br />
Slides are on the ParaSail google group:<br />
<a href="https://groups.google.com/forum/#!topic/parasail-programming-language/hMiRrQijNPg">https://groups.google.com/forum/#!topic/parasail-programming-language/hMiRrQijNPg</a> Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com2tag:blogger.com,1999:blog-8383004232931899216.post-50754947969705193052013-01-25T13:21:00.000-05:002013-01-25T13:21:48.296-05:00The ParaSail "import" clause -- library level visibilityWe have postponed implementing the "import" clause for <b>ParaSail</b> 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 <span style="font-family: "Courier New",Courier,monospace;">Acme::Killer_App::Driver</span>). This works fine for small programs, but as programs grow larger, there is often a desire to be more <i>restrictive</i> (on the one hand) as far as interdependencies, and provide a <i>shorthand</i> (on the other hand) for long module names.<br />
<br />
So now in ParaSail, you can both restrict visibility, and create shorthands, using a (Java-like) import clause:<br />
<br />
<span style="font-family: "Courier New",Courier,monospace;"> import Acme::Killer_App::Driver</span><br />
<br />
will both give visibility on this <span style="font-family: "Courier New",Courier,monospace;">Driver</span> module, and provide a shorthand of simply "<span style="font-family: "Courier New",Courier,monospace;">Driver</span>" 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:<br />
<br />
<span style="font-family: "Courier New",Courier,monospace;"> import Acme::Killer_App::* </span><br />
<br />
gives visibility on <span style="font-family: "Courier New",Courier,monospace;">Acme::Killer_App::Driver,</span> <span style="font-family: "Courier New",Courier,monospace;">Acme_Killer_App::Utilities</span>, etc. as well as allowing the use of the shorthand names "<span style="font-family: "Courier New",Courier,monospace;">Driver</span>" and "<span style="font-family: "Courier New",Courier,monospace;">Utilities</span>" directly in the source code that follows the import clause.<br />
<br />
In the absence of <i>any</i> applicable import clauses, a <i>default</i> is provided based on the name of the module being compiled. If the module being compiled has the name "<span style="font-family: "Courier New",Courier,monospace;">A::B::C</span>" then the default import clause, when none is supplied, is "<span style="font-family: "Courier New",Courier,monospace;">import A::B::*</span>". That is, the module has visibility on the entire hierarchy of modules rooted at its <i>parent</i> module <span style="font-family: "Courier New",Courier,monospace;">A::B</span>, and can use the names of its <i>sibling</i> modules directly as a shorthand (e.g. can refer to <span style="font-family: "Courier New",Courier,monospace;">A::B::D</span> as simply "<span style="font-family: "Courier New",Courier,monospace;">D</span>").<br />
<br />
Whether or not <i>explicit</i> import clauses apply to a piece of ParaSail source code, the following two <i>implicit</i> import clauses <i>always</i> apply:<br />
<br />
<span style="font-family: "Courier New",Courier,monospace;"> import PSL::Core::*</span><br />
<span style="font-family: "Courier New",Courier,monospace;"> import PSL::Containers::*</span><br />
<br />
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.<br />
<br />
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 <i>inheritance</i> or <i>accumulation</i> of import clauses. Only one set applies at a time (after always adding in the implicit ones for PSL::Core::* and PSL::Containers::*).<br />
<br />
So why did we choose this particular approach for the import clause, and how does it compare to that of other languages?<br />
<br />
Programming languages take many different approaches to controlling visibility between standalone program units defined at the top level of some source file. <i>C</i> and <i>C++</i> use a strictly <i>textual</i> #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.<br />
<br />
Languages like <i>Modula</i>, <i>Ada</i>, <i>Java</i>, etc., adopted a <i>module-based</i> approach to standalone unit visibility, where an <span style="font-family: "Courier New",Courier,monospace;">import</span> clause or a <span style="font-family: "Courier New",Courier,monospace;">with</span> 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 <i>programming language</i> name rather than their <i>file</i> 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 <i>package-visible</i> 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.<br />
<br />
Note that Ada does allow the <i>body</i> of a library unit to <i>inherit</i> the <span style="font-family: "Courier New",Courier,monospace;">with</span> clauses from its <i>spec</i>, as well as from its <i>parent</i> units in the library unit hierarchy. Hence a <span style="font-family: "Courier New",Courier,monospace;">with</span> 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.<br />
<br />
The new language <i>Go</i> has an interesting approach, where <i>filenames</i> 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.<br />
<br />
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.<br />
<br />
Another dimension over which importing differs is the provision of <i>shorthands</i> 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.<br />
<br />
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").<br />
<br />
So now back to the approach adopted for ParaSail. ParaSail follows the Java model as far as <i>shorthands</i>, in that an "<span style="font-family: "Courier New",Courier,monospace;">import Acme::Killer_App::Driver</span>" has the effect of making "<span style="font-family: "Courier New",Courier,monospace;">Driver</span>" usable directly within the code that follows. But unlike in Java, if the programmer gives explicit import clauses, then they <i>restrict</i> 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.<br />
<br />
ParaSail also eschews any <i>inheritance</i> 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. Tucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.com0