ParaSail Programming Language

[Tuck]

Over the past six months I have been describing the design of a new
programming language called "ParaSail" in a "blog":

http://parasail-programming-language.blogspot.com

Readers, commenters, kibitzers, lurkers, etc. are very welcome.

Below is a quick summary. Please see the blog for more details.

ParaSail stands for "Parallel Specification and Implementation
Language," and is designed with the principle that if you want
programmers to write parallel algorithms, you have to immerse them in
parallelism, and force them to work harder to make things sequential.
In ParaSail, parallelism is everywhere, and threads are treated as
resources like virtual memory -- a given computation can use 100s of
threads in the same way it might use 100s of pages of virtual memory.
ParaSail supports both lock-based and lock-free concurrent objects.

ParaSail also supports annotations, and in fact requires them in some
cases if they are needed to prove that a given operation is safe. In
particular, all checks that might normally be thought of as run-time
checks (if checked by the language at all) are compile-time checks in
ParaSail. This includes uninitialized variables, array index out of
bounds, null pointers, race conditions, numeric overflow, etc. If an
operation would overflow or go outside of an array given certain
inputs, then a precondition is required to prevent such inputs from
being passed to the operation. ParaSail is designed to support a
"formal" approach to software design, with a relatively static model
to simplify proving properties about the software, but with an
explicit ability to specify run-time polymorphism where it is needed.

ParaSail has only four basic concepts -- Modules, Types, Objects, and
Operations. Every type is an instantiation of a module. An object is
an instance of some type. An operation operates on objects.

There are no global variables. Any object to be updated by an
operation must be an explicit input or output to the operation.

ParaSail has user-defined indexing (analogous to arrays or tables),
user-defined literals (integers, reals, strings, characters, and
enums), user-defined "aggregates," etc. Every type is the
instantiation of some module, including those that might be considered
the built-in types, and there are no "special" operators or constructs
that only a built-in type can utilize.

ParaSail has no pointers, though it has references, optional and
expandable objects, and user-defined indexing, which together provide
a rich set of functionally equivalent capabilities without any hidden
aliasing nor any hidden race conditions.

That's probably enough motherhood for now...

-Tuck

P.S. Here is a parallel "N" Queens solution in ParaSail (or at least I
think it is, since ParaSail is still being designed). The blog talks
more about this example:

interface N_Queens <N : Univ_Integer := 8> is
// Place N queens on a checkerboard so that none of them can
// "take" each other.
type Chess_Unit is new Integer<-N*2, N*2>;
type Row is Chess_Unit {Row in 1..N};

function Place_Queens() -> Vector<Vector<Row>>
{for all I in Keys(Place_Queens) : Length(Place_Queens[I]) ==
N};
end interface N_Queens;

class N_Queens <N : Univ_Integer := 8> is
type Column is Chess_Unit {Column in 1..N};
type Sum_Range is Chess_Unit {Sum_Range in 2..2*N};
type Diff_Range is Chess_Unit {Diff_Range in (1-N) .. (N-1)};
type Sum is Set<Sum_Range>;
type Diff is Set<Diff_Range>;
exports
function Place_Queens() -> Vector<Vector<Row>>
{for all I in Keys(Place_Queens) : Length(Place_Queens[I]) == N}
is
var Solutions : concurrent Vector<Vector<Row>> := [];

*Outer_Loop*
for (C : Column := 1; Trial : Vector<Row> := [];
Diag_Sum : Sum := []; Diag_Diff : Diff := []) loop
// Iterate over the columns

for R in Row concurrent loop
// Iterate over the rows
if (R+C) not in Diag_Sum and then
(R-C) not in Diag_Diff then
// Found a Row/Column combination that is not on any
diagonal
// already occupied.
if C < N then
// Keep going since haven't reached Nth column.
continue loop Outer_Loop with (C => C+1,
Trial => Trial | R,
Diag_Sum => Diag_Sum | (R+C),
Diag_Diff => Diag_Diff | (R-C));
else
// All done, remember trial result.
Solutions |= Trial;
end if;
end if;
end loop;
end loop Outer_Loop;
return Solutions;

end function Place_Queens;
end class N_Queens;