Muster: An Implicitly Parallel Programming Language

With the increase in multi-core CPUs, taking advantage of available system resources when writing new applications has grown more difficult. It is not impossible to create well-performing systems on the current (and next) generation of hardware, however, the current programming languages are built with the assumption of sequential operation. Muster is a fundamental change in the approach. Rather than adding mechanisms to ease parallel development in existing languages, Muster assumes that operations in given contexts will implicitly be run in parallel and the developer must explicitly state when they should be run serially. This approach causes the serial algorithms to be much more painful to implement than parallel algorithms. The core idea is to provide an environment where the natural mental model is that of a parallel approach to the problem rather than a serial one.

A Muster Language Primer

Muster uses many familiar concepts in programming languages, but some of them in unique ways and with its own nomenclature. This section is designed around getting someone up to speed on reading the syntax and understanding the concepts of Muster as quickly as possible.

Declarations

At its core, Muster represents everything as a declaration. A declaration is a block of statements and operations that optionally takes an input and optionally has an output. The values used in a declaration are resolved at run time, allowing values to be "closed over".

/* Declares a block that takes no inputs and when evaluated the value of the declaration is the string "a" */
declare () {
  "a";
};

/* Declares a block that takes a single input, 'inA', that must satisfy the type requirements of being supplied
 * to the block std.out.  When evaluated, the supplied value is passed to std.out and the value of the declaration
 * is the result of passing inA to std.out.
 */
declare (inA) {
  std.out << inA;
};

/* Declares a block that takes a single input, 'inB', that must be of the type java.lang.String.  When evaluated,
 * the supplied value is passed to std.out and the value of the declaration is the result of passing inB to std.out.
 */
declare (inB: java.lang.String) {
  std.out << inB;
};

/* Declares a block that takes a single input, 'inC', that must be of the type java.lang.Integer.  A declaration
 * is embedded in the first.  Whenever the inner declaration is called, inC holds the value supplied to the
 * outer declaration for that particular instance.
 */
declare (inC: java.lang.Integer) {
  declare () {
    inC;
  };
};

Definitions

A definition in Muster is how a block is provided a label to be used later. Whenever the label is encountered, the block associated with the definition is evaluated. Muster allows for forward references without requiring forward definitions.

/* Defines a label 'toString' that, when evaluated, will evaluate the definition toString on the supplied item.
 * The supplied item must contain a definition of toString.
 */
define toString := declare (in) {
  in.toString;
};

/* Defines a label 'std' to contain a declaration with no inputs that holds two definitions, 'out' and 'err'.  Both
 * namespacing and types are accomplished this way.  Contained definitions are not available unless the 'std'
 * definition is referenced.
 */
define std := declare () {
  define out := declare (in) {
    System.out.println(in);
  };

  define err := declare (in) {
    System.err.println(in);
  };
};
std.out << "Hello World!\n";
std.err << "Error World!\n";

Type System

Muster is strongly typed and uses an Object-Oriented approach similar to the Go programming language. Any declaration (and definition since a definition is just a label for a declaration) can be used as a type 'template'. Given:

define A := declare(in: java.lang.String) {
  define reverse := declare () {}
  define length := declare () {}
};

The definition A describes a type that takes a java.lang.String on creation and the resulting entity has two definitions that can be resolved from it, reverse and length. This definition can be used by calling:

define a := declare () {
  A << "test";
};

/* Runtime error, reverse does not evaluate to a value */
System.out.println << a.reverse;

A second definition, Aprime can implement the same capabilities as A and be used in the same way A could be.

define Aprime := declare(in: java.lang.String) {
  define reverse := declare () {
    define buffer := declare () {
      new << java.lang.StringBuffer << in;
    };

    buffer.reverse.toString;
  };

  define length := declare () {
    in.length;
  };
};

Aprime can now be used anywhere that is described as taking an A.

define reverseString := declare (in: A) {
  A.reverse;
};

define myAprime := declare () {
  Aprime << new << java.lang.String << "Hello!";
};

/* Prints '!olleH' to STDOUT */
System.out.println << reverseString << myAprime;

Namespacing occurs by implicitly creating an object with the available definitions and is simply just a type with no input parameters. When dealing with types and namespaces, a '.' references a contained definition. If the definition doesn't require input parameters, the definition name may be used. If it requires input parameters, a new definition wrapping it that supplies inputs is required (or the inputs must be declared inline).

Declaring inputs inline:

/* () defines a 'composite', a 0 or more list of values, each if which is evaluated prior to other calls */
/* Prints '!eybdooG' to STDOUT */
System.out.println << (Aprime << "Goodbye!").reverse;

Function Decomposition

Muster has a unique dispatch system for evaluating blocks based on the inputs supplied for a given block. If a list of items are supplied to a block that does not take a list as input, the block is evaluated multiple times for each set of matching input.

/* A definition that takes a single value as input */
define A := declare (in: Item) { in; };
/* A definition that takes two values as input */
define B := declare (inA: Item, inB: Item) { (inA, inB); };
/* A definition that takes an item and a list as input */
define C := declare (in: Item, rest: List[Item]) { (in, rest); };
/* A definition that takes a list as input */
define D := declare (in: List[Item]) { in; };

/* Calls A as A("x"), A("y"), A("z") */
A << ("x", "y", "z");
/* Calls B as B("x","y"), B("z",null) */
B << ("x", "y", "z");
/* Calls C as C("x", ("y","z")) */
C << ("x", "y", "z");
/* Calls D as D(("x","y","z")) */
D << ("x", "y", "z");
/* Calls B as B("x","a"), B("y","b"), B("z","c") */
B << (("x","y","z"),("a","b","c"));

This lends to significantly simpler code for how to perform a large variety of operations. It also reduces a large amount of code used only for managing collections of items.

Conditinal Statements and Loops

Muster does not have an explicit loop construct. The design of the language is such that nearly all cases where a loop is required, using the function decomposition model is much more elegant and efficient. Muster fully supports recursion, so algorithms that use a recursive style loop will work cleanly.

Muster has a single conditional statement, when. When operates like a declaration block except that it is only evaluated when the statements evaluate to a truthy value.

define A := declare (in: String) {
  when (in.equals << "test") {
    System.out.println << in;
  };
};

/* Prints 'test' */
A << "test";
/* Doesn't print anything */
A << "nottest";

The logic behind this model is that conditional expressions are used for flow control and validation. With Muster's function decomposition model, flow control is built in at the call level and the only remaining need is for validation. There is currently nothing to compare to an "else" statement, but may be added or handled at a later time if it becomes an obvious need.

Implicitly Parallel, Explicitly Serial

In Muster, a statement is a single expression that can be evaluated. An operation is a series of statements, each fed data from another statement.

Statements:
"x"
Foo.bar
values

Operations:
std.out << "x";
std.out << sort << ("d","c","a","b");

A single operation (series of statements) executes in parallel while a series of operations execute serially.

/* Each statement can be in process simultaneously */
/* Prints:
 * xyz OR
 * xzy OR
 * yxz OR
 * yzx OR
 * zxy OR
 * zyx
 */
std.out << ("x","y","z");

/* Operations are executed in sequence */
/* Prints:
 * Hello
 * There
 */
std.out << "Hello\n";
std.out << "There\n";

The way that operations execute in parallel is determined by the signature of the definitions being called. If a definition A produces a list and is 'fed' into a definition B that takes a single item, B will be called in parallel, once for each item produced from A. If a definition C produces a single item and a definition D takes a list of items, all the results of C will be collected and fed into D at once.

/* A := (in: Item)
 * B := (in: List[Item])
 * C := (in: Item)
 * D := ("x","y","z")
 */
/* D is evaluated, resulting in a composite with values "x","y" and "z".  A takes a single item, so it is called
 *   in parallel as A("x"), A("y"), A("z").
 * B takes a List[Item], so all the results of A() are collected and B is called with the results.  The results from
 *   A can be in any order.
 * C takes an Item, so if B returns a single item, it is fed into C.  If B returns a List, B is called once for
 *   each item in the list.
 * The results of C are collected and are the result of the operation.
 */
C << B << A << D;

There are times when a combination of statements within an operation must be called serially. This may be to preserve list order or to enforce the order of execution of statements. This is accomplished by wrapping the call in a 'serial' block.

/* A := (in: Item)
 * B := (in: List[Item])
 * C := (in: Item)
 * D := ("x","y","z")
 */
/* D is evaluated, resulting in a composite with values "x", "y" and "z".  A takes a single item, but is within a
 *   serial block, so A is called as A("x") then A("y") then A("z").
 * B takes a List[Item], so all the results of A() are collected and B is called with the results.
 * C takes an Item, so if B returns a single item, it is fed into C.  If B returns a List, B is called once for
 *   each item in the list.
 * The results of C are collected and are the result of the operation.
 */
C << B << serial { A << D };

This makes up the fundamental parallelism that Muster provides. With these simple rules in mind, the mental and algorithmic model of an application naturally expose themselves as parallel operations.

A Simple Program

Here is an example program that is commonly used as a simple filter for development jobs, FizzBuzz. Given a number n, for 1..n inclusive, print Fizz if the number is divisible by 3, Buzz if the number is divisible by 5 and just the number if it's not divisible by either, in order.

/* Main entrypoint of the application.  'in' is a List of strings supplied on the command line. */
define main := declare (in: List) {
  /* Pass 'in' to the definition 'head' (retrieves the first element in a list).
   * The result is passed into the definition java.lang.Integer.parseInt (returns an integer or throws exception).
   * The integer is supplied to SimpleFizzBuzzer, which runs the actual logic in a simple manner.
   */
  SimpleFizzBuzzer << (java.lang.Integer.parseInt << head << in);
  /* Pass 'in' to the definition 'head' (retrieves the first element in a list).
   * The result is passed into the definition java.lang.Integer.parseInt (returns an integer or throws exception).
   * The integer is supplied to ParallelFizzBuzzer, which runs the actual logic in parallel while still
   *   outputting the results in the proper order.
   */
  ParallelFizzBuzzer << (java.lang.Integer.parseInt << head << in);
};

/* A simple definition that performs FizzBuzz recursively */
define SimpleFizzBuzzer := declare (in: java.lang.Integer) {
  /* Call doFizzBuzz with a value of 0 */
  doFizzBuzz << 0;

  /* doFizzBuzz, the actual logic for performing the algorithm.  Note that doFizzBuzz holds the value that
   * was passed to SimpleFizzBuzzer ('in').
   */
  define doFizzBuzz := declare (index: java.lang.Integer) {
    /* When index modulus 3 is 0, print 'Fizz' */
    when (equal << (modulus << (index,3), 0)) {
      System.out.println << "Fizz";
    };
    /* When index modulus 5 is 0, print 'Buzz' */
    when (equal << (modulus << (index,5), 0)) {
      System.out.println << "Buzz";
    };
    /* When index modulus 15 is not 0, print the number */
    when (notEqual << (modulus << (index,15), 0)) {
      System.out.println << in.toString;
    };

    /* Prints out a new line */
    System.out.println << "\n";

    /* When index is not equal to in */
    when (notEqual << (index, in)) {
      /* Call doFizzBuzz with index plus 1 */
      doFizzBuzz << (plus << (index, 1));
    };
  };
};

/* Parallel version */
define ParallelFizzBuzzer := declare (in: java.lang.Integer) {
  /* Evaluated when ParallelFizzBuzzer is evaluated.
   * Generates a sequence from 0 to in inclusive.
   * Calls doFizzBuzz once for each value in the sequence (in parallel)
   * Calls sort on all the results from the doFizzBuzz calls (takes a list of integer,item pairs and sorts).
   * Calls printFizzBuzz with the sorted list.
   */
  printFizzBuzz << sort << doFizzBuzz << generateSequence << (0, in);

  /* The main logic.  Takes a single integer and returns (integer, (Fizz|Buzz|FizzBuzz|integer)) depending
   * on the result of the algorithm.
   */
  define doFizzBuzz := declare (value: java.lang.Integer) {
    /* Concatenates the results of evaluating doFizz, doBuzz, doNumber and "\n" together and
     * returns a composite of (value, <result>)
     */
    (value, concat << (doFizz, doBuzz, doNumber, "\n"));

    /* When evaluated, returns "Fizz" or an empty string */
    define doFizz := declare () {
      when (equal << (modulus << (value,3), 0)) {
        "Fizz";
      };
    };
    /* When evaluated, returns "Buzz" or an empty string */
    define doBuzz := declare () {
      when (equal << (modulus << (value,5), 0)) {
        "Buzz";
      };
    };
    /* When evaluated, returns the string of the value or an empty string */
    define doNumber := declare () {
      when (notEqual << (modulus << (value,15), 0)) {
        value.toString;
      };
    };
  };

  define printFizzBuzz := declare (index: java.lang.Integer, string: java.lang.String) {
    System.out.println << string;
  };
};