First Impressions of the Fortress Language

Published:03/08/2012   Last Updated:03/08/2012

Posted by Pablo Halpern on Fri, May 08, 2009

 

I was privileged recently to attend a one-day hands-on introduction to Fortress lead by Sukyoung Ryu and Jan-Willem Maessen of Sun Microsystems and hosted by MIT.  Fortress is a new parallel programming language developed at Sun and designed to bring together many of the best ideas in computer language design from the last few decades.   Some of the highlights are:

  • Implicit parallelism using a Cilk-style work-stealing scheduler
  • Transactional synchronization to minimize contention on shared objects
  • An extensible syntax that uses mathematical symbols
  • Static type-checking with polymorphism and type inference
  • Definition of many language features through libraries rather than built-in syntax
  • Support for generic, object-oriented, and functional programming paradigms
  • Garbage collection
  • Write-once-run-anywhere coding enabled by using the Java Virtual Machine (JVM)

There is a lot to Fortress, and I will only touch on a few topics here.

Mathematical Notation

Fortress’s syntax has little in common with languages like C++ or Java.  In fact, it is unlike any other programming language I’ve seen (including Lisp, Perl, sh, FORTRAN, and APL).  I am told that it bears a vague resemblance to Haskell, though there are features that are drawn from many different sources including some that would be familiar to C++ or even Pascal programmers.

The most striking thing one first notices about Fortress syntax is the use of mathematical notation.  The following code defines a function that takes a list of strings and returns true if any of the strings have the value, “hello”:

The code above can also be represented in plain text as follows:

 

hasHello(xs: List[\String\]): Boolean =
BIG OR[x <- xs] x="Hello"

 

Depending on your point of view, either the first notation is an ornamental rendering of the second, or the second notation is a primitive representation of the first (for people using impoverished editing and source-control tools). Using emacs or vim in Fortress mode, you can enter plain text and it will be partially rendered into the mathematical form as you type:

Before I did any work in Fortress, the graphical rendering seemed gimmicky to me.  After doing a few exercises, however, it started to grow on me.  Though I doubt that the notation alone is enough to make Fortress easy for a mathematician to use, I have to admit that it does make the program easier to read once you get used to it.  It’s kind of like a pretty-printer on steroids – not limited to just bolded keywords and italicized comments.

Extensible syntax

More profound than the mathematical notation is the fact that the syntax is extensible.  There wasn’t much talk of extending the syntax in the one-day workshop, but one mechanism that was mentioned was the ability to overload whitespace.  If you’ve read Bjarne Stroustrup’s April Fool’s Day proposal for overloadable whitespace in C++ (PDF), you probably got a chuckle out of that last sentence.  But Fortress really does, in a sense, allow whitespace to be overloaded so that two times x is written simply as 2 x.  More precisely, what is being overloaded is not the whitespace, but the juxtaposition of tokens.  Thus two times x can be written even more simply as 2x, with no intervening whitespace.

Fortress’s syntax is so extensible, that during this short workshop I could not tell which parts of the language are baked into its syntax, and which parts are provided by libraries, just as cout<< may look like a C++ intrinsic to a newbie C++ programmer. This blurring of intrinsic syntax and library-provided syntax is apparently deliberate in Fortress.

Types and Dynamic Overloading

The Fortress type system lets the user define traits, which are like Java Interfaces or C++ pure abstract classes and objects which are like Java or C++ classes.  A function argument type can be declared using either a trait or object type and functions can be overloaded.  A function call is type-checked at compile-time to ensure that there is only one best-match for an overload set, but the actual resolution of the function overload is preformed at run-time based on the dynamic type of all of the arguments.  Contrast this dynamic function resolution to C++’s template instantiation, which occurs entirely at compile time based on static argument types, or C++’s virtual function binding (or Java’s member-function call), which occurs at run-time based on the dynamic type of the implicit this argument but the static types of all of the remaining arguments.

Parallelism

Of course, what interested me the most about Fortress was its model and mechanism for parallel programming.  The Fortress team consists of some very smart people, so it was with some satisfaction that I read on their web site that their parallel scheduler uses essentially the same work-stealing algorithm as Cilk++.  Unfortunately, the underlying JVM does not provide the stack-manipulation primitives needed for a maximally-efficient work-stealing scheduler.  (Providing such primitives would probably invite security exploits.)  I suspect that the JVM, with some guidance from the Fortress team, will someday evolve to support work-stealing natively.

Implicitly, Fortress performs the equivalent of a cilk_spawn whenever it sees two parts of an expression that can be executed in parallel.  For example, in the familiar recursive implementation of a function that computes a Fibonacci number,

fib(n: ZZ32): ZZ32 =
if n < 2 then n
else fib(n - 1) + fib(n - 2)
end;


the two recursive calls to fib() are invoked in parallel.  The equivalent code in Cilk++ would be:

int fib(int n) {
if (n < 2) return n;
a = cilk_spawn fib(n – 1);
b = fib(n – 2);
cilk_sync;
return a + b;
}


For this to work, it is important that that fib has no side-effects, otherwise a data race may occur.  One must be very careful when calling functions with side-effects, lest the same side-effect occur in multiple parts of a parallel expression.  (Even in serial languages like C++, performing side-effects on the same memory location in multiple branches of the same expression is never recommended because you cannot control the order in which the side-effects will occur.)  In addition to this implicit parallelism, the language supports some explicit parallel constructs:

  • A for loop is parallel by default.
  • A do also construct specifies two or more blocks that may execute in parallel with one another.

Fortress provides at least two mechanisms for coordinating access to shared variables in parallel operations: atomic operations and reductions.  Atomic operations use Fortress’s transactional memory system to ensure that one or more operations occur atomically, but with minimal locking and contention.  Atomic operations prevent data races, but do not by themselves ensure determinism or serial semantics.  Reductions are constructs that perform associative operations in parallel and preserve serial semantics, like Cilk++ reducers.  The hasHello example, above, uses a BIG OR reduction to compute its result.

Immutable data types

The ability to use both implicit and explicit parallelism is enhanced by the Fortress library’s orientation towards immutable data structures.  An immutable data structure is one that supports no modifying operations.  This is not to be confused with a read-only (constant) variable, which is simply an immutable view on an otherwise mutable data structure.  A variable of immutable type can be re-assigned, but only by binding it to a different object – the original object remains unchanged. (In Fortress, as in Java and most other garbage-collected languages, a variable does not hold an object, but rather a reference to an object.  Assigning a variable causes it to be bound to a different object.) To better understand immutable data types, consider the following expression, which takes a list x and removes the third element:

x := x.take(2) || x.drop(3);


The two halves of the expression each return new lists holding a subsequence of x (take(2) returns the first two elements, drop(3) returns all but the first three elements), leaving x itself unmodified.  The ||  operator returns a third new list holding the concatenation of its operands.  Finally, the variable x is reassigned to refer to the return value from ||.  The original list may or may not still be referenced somewhere else in the program, but it remains unchanged by this expression (or any other expression).  The garbage collector is responsible for freeing the original list (if it is no longer used), as well as the temporary lists returned by take() and drop().

Using immutable objects makes it easier for both humans and compilers to reason about the parallelism in a program.  Given two operations on an object belonging to an immutable type, it is readily apparent that the two operations may be performed in parallel because there are no side effects that could change the value of an immutable object.  Immutable data types are an important part of functional programming, so Fortress’s library of immutable types encourages the use of a functional programming style, to some degree, and is a significant paradigm shift from imperative programming.  As a long-time C++ programmer, I found that programming in Fortress exercised a part of my brain that had not been used much since my Lisp programming days in college.

What Next?

The current interpreter and compiler are far from being commercial products and both the language and the library are in flux, so don’t expect Fortress to solve your current parallelization problems.  Performance is further hampered by limitations in the current JVM specification (including the absence of optimized tail recursion, which hurts many divide-and-conquer algorithms). Even if an industrial-strength development environment becomes available, legacy code in languages like C++ cannot easily be ported to Fortress.

Nevertheless, Fortress is an interesting research project that has the potential to advance the field of programming in general, and parallel programming specifically.  A native (non-JVM) compiler could conceivably generate code that would run on the Cilk++ runtime platform. I hope that Sun (and now Oracle) will continue to support the Fortress project.  The industry needs projects like Fortress to continue generating fresh ideas.

For more information about Fortress, see the Project Fortress Community web site.

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.