Archive for the ‘Functional D’ Category

Functional D: Is Transitive Const Fundamental?

July 30th, 2008 14 comments

As I’ve mentioned before, a pure functional subset is forming in the D Programming Language. According to the creators of D, transitive const is a key feature to make this work.

The future of programming will be multicore, multithreaded. Languages that make it easy to program them will supplant languages that don’t. Transitive const is key to bringing D into this paradigm. […] C++ cannot be retrofitted to supporting multiprogramming in a manner that makes it accessible. D isn’t there yet, but it will be, and transitive const will be absolutely fundamental to making it work.

[Quote from the D website]

What is transitive const?

Just a quick explanation for those of us who doesn’t have academic terms in close memory. Transitivity is a property of some binary relations, for example equality:

if A = B and B = C, then A = C

Applied to the concept of const it means, simply put, that anything reachable from a const type is also a const. So, for a declaration const int **p, p is const, as well as *p and **p.
The same is true in the case of composite types:

class A {
  int f;

  void set_f(int a_value) {
    f = a_value;

const A a = new A();
a = new A(); // error
a.a = 2; // error
a.set_a(2); // error

All three reassignments above result in compiler errors due to the fact that a is const, and anything reachable from it is also const.

Why does it matter?

So, in what way is transitive const fundamental to concurrent programming? Well, it isn’t. What Walter Bright and his companions refer to is the fact that pure functional programming is thread-safe by design. That is, in a pure functional language the result of a function is solely dependent on its arguments. Thus, in a code like this:

val = some_func( a(), b(), c() );

functions a(), b() and c() can be safely executed concurrently in a multi-core architecture; Nothing a(), b() or c() does can affect each others results. This is not the case for imperative languages that builds on the notion of mutable and global state. With mutable state comes hidden side-effects (a(), b() or c() could change common data and cause raise conditions) that complicates multi-thread programming so much.

What the people behind D tries to do is to create a pure functional subset within the language. I like to refer to it as Functional D. Such a subset would allow us to write code that is thread-safe by default, all you have to do is to write Functional D code. The compiler would then be able to chisel out the functional code and fully utilize the advantages of functional programming.

Immutable data and pure functions are fundamental

To make this work we need a way to make data immutable and a way to shut down access to the global state. In D you use the invariant keyword to create immutable data. The pure keyword is used to mark functions that may only take invariant arguments, no access to the global state, and that may only invoke other pure functions. (As of this writing, the semantics of the pure keyword is not yet implemented).

int g = 0;

pure int pure_func(invariant int a) {
  a = 0; // error, a is invariant
  g = 1; // error, can't write to global g
  writefln(a); // error, writefln is not pure
  return g + a; // error, can't read global g

How does transitive const fit into all of this? To use the intuitive definitions from Andrei Alexandrescu’s slides on the functional subset of D:

  • const(T) x: I can’t modify x or anything reachable from it
  • invariant(T) x: Nobody can modify x or anything reachable from it

Const is not strong enough to be used in the functional subset (which depends on truly immutable data), but it has one application that could be important. From Walter Bright at the D newsgroup:

Const allows you to reuse code that works on invariants to work with
mutables, too.

How usable is const to the functional subset?

Const can be used to write code that works with data from both the imperative (mutable) and the functional (immutable) subsets. For example, the print function below.

void print(const int a) {

const int a = 1;
print(a); // ok

invariant int b = 2;
print(b); // ok

print(3); // ok

The reason this works is that invariants and immutable data is implicitly converted to const when necessary. One can question how useful this would be in practice though, the print function above would not be invokable from the functional subset (which would require it to be pure).

My conclusion is that although it may very well be important, transitive const is not “absolutely fundamental to making it work.” Transitive invariant, on the other hand, is.