SequenceL
SequenceL is a general purpose functional programming language and auto-parallelizing compiler and tool set, whose primary design objectives are performance on multi-core processor hardware, ease of programming, platform portability/optimization, and code clarity and readability. Its main advantage is that it can be used to write straightforward code that automatically takes full advantage of all the processing power available, without programmers needing to be concerned with identifying parallelisms, specifying vectorization, avoiding race conditions, and other challenges of manual directive-based programming approaches such as OpenMP.
Programs written in SequenceL can be compiled to multithreaded code that runs in parallel, with no explicit indications from a programmer of how or what to parallelize., versions of the SequenceL compiler generate parallel code in C++ and OpenCL, which allows it to work with most popular programming languages, including C, C++, C#, Fortran, Java, and Python. A platform-specific runtime manages the threads safely, automatically providing parallel performance according to the number of cores available, currently supporting x86, POWER8, and ARM platforms.
History
SequenceL was initially developed over a 20-year period starting in 1989, mostly at Texas Tech University. Primary funding was from NASA, which originally wanted to develop a specification language which was "self-verifying"; that is, once written, the requirements could be executed, and the results verified against the desired outcome.The principal researcher on the project was initially Dr. Daniel Cooke, who was soon joined by Dr. Nelson Rushton and later Dr. Brad Nemanich. The goal of creating a language that was simple enough to be readable, but unambiguous enough to be executable, drove the inventors to settle on a functional, declarative language approach, where a programmer describes desired results, rather than the means to achieve them. The language is then free to solve the problem in the most efficient manner that it can find.
As the language evolved, the researchers developed new computational approaches, including consume-simplify-produce. In 1998, research began to apply SequenceL to parallel computing. This culminated in 2004 when it took its more complete form with the addition of the normalize-transpose semantic, which coincided with the major vendors of central processing units making a major shift to multi-core processors rather than continuing to increase clock speeds. NT is the semantic work-horse, being used to simplify and decompose structures, based on a dataflow-like execution strategy similar to GAMMA and NESL. The NT semantic achieves a goal similar to that of the Lämmel and Peyton-Jones’ boilerplate elimination.
All other features of the language are definable from these two laws - including recursion, subscripting structures, function references, and evaluation of function bodies.
Though it was not the original intent, these new approaches allowed the language to parallelize a large fraction of the operations it performed, transparently to the programmer. In 2006, a prototype auto-parallelizing compiler was developed at Texas Tech University. In 2009, Texas Tech licensed the intellectual property to Texas Multicore Technologies, for follow-on commercial development. In January 2017 TMT released v3, which includes a free Community Edition for download in addition to the commercial Professional Edition.
Design
SequenceL is designed to be as simple as possible to learn and use, focusing on algorithmic code where it adds value, e.g., the inventors chose not to reinvent I/O since C handled that well. As a result, the full is only 40 pages, with copious examples, and its formal grammar has around 15 production rules.SequenceL is strictly evaluated, statically typed with type inference, and uses a combination of infix and prefix operators that resemble standard, informal mathematical notation. It is a purely declarative language, meaning that a programmer defines functions, in the mathematical sense, without giving instructions for their implementation. For example, the mathematical definition of matrix multiplication is as follows:
The SequenceL definition mirrors that definition more or less exactly:
matmul, B) :=
let k := 1...size;
in sum;
The subscripts following each parameter A and B on the left hand side of the definition indicate that A and B are depth-2 structures, which are here thought of as matrices. From this formal definition, SequenceL infers the dimensions of the defined product from the formula for its 'th entry and computes each entry by the same formula as in the informal definition above. Notice there are no explicit instructions for iteration in this definition, or for the order in which operations are to be carried out. Because of this, the SequenceL compiler can perform operations in any order which satisfies the defining equation. In this example, computation of coordinates in the product will be parallelized in a way that, for large matrices, scales linearly with the number of processors.
As noted above, SequenceL has no built-in constructs for input/output since it was designed to work in an additive manner with other programming languages. The decision to compile to multithreaded C++ and support the 20+ Simplified Wrapper and Interface Generator languages means it easily fits into extant design flows, training, and tools. It can be used to enhance extant applications, create multicore libraries, and even create standalone applications by linking the resulting code with other code which performs I/O tasks. SequenceL functions can also be queried from an interpreter with given inputs, like Python and other interpreted languages.
Normalize–transpose
The main non-scalar construct of SequenceL is the sequence, which is essentially a list. Sequences may be nested to any level. To avoid the routine use of recursion common in many purely functional languages, SequenceL uses a technique termed normalize–transpose, in which scalar operations are automatically distributed over elements of a sequence. For example, in SequenceL we haveThis results not from overloading the '+' operator, but from the effect of NT that extends to all operations, both built-in and user-defined.
As another example, if f is a 3-argument function whose arguments are scalars, then for any appropriate x and z we will have
The NT construct can be used for multiple arguments at once, as in, for example
It also works when the expected argument is a non-scalar of any type T, and the actual argument is a list of objects of type T. For example, if A is a matrix and Xs is a list of matrices , and given the above definition of matrix multiply, in SequenceL we would have
matmul =
As a rule, NTs eliminate the need for iteration, recursion, or high level functional operators to
- do the same things to every member of a data structure, or to
- process corresponding parts of similarly shaped structures together.
Example: prime numbers
A good example that demonstrates the above concepts would be in finding prime numbers. A prime number is defined asSo a positive integer z is prime if no numbers from 2 through z-1, inclusive, divide evenly. SequenceL allows this problem to be programmed by literally transcribing the above definition into the language.
In SequenceL, a sequence of the numbers from 2 through z-1, inclusive, is just, so a program to find all of the primes between 100 and 200 can be written:
prime := z when none;
Which, in English just says,
If that condition isn’t met, the function returns nothing. As a result, running this program yields
cmd:>prime
17
cmd:>prime
empty
The string "between 100 and 200" doesn’t appear in the program. Rather, a programmer will typically pass that part in as the argument. Since the program expects a scalar as an argument, passing it a sequence of numbers instead will cause SequenceL to perform the operation on each member of the sequence automatically. Since the function returns empty for failing values, the result will be the input sequence, but filtered to return only those numbers that satisfy the criteria for primes:
cmd:>prime
In addition to solving this problem with a very short and readable program, SequenceL’s evaluation of the nested sequences would all be performed in parallel.