Posts Tagged ‘functional programming’

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.


The Future of D is Functional

April 16th, 2008 20 comments

The D Programming Language has an impressive list of cool features. That is not always a good thing. A feature should contribute to the philosophy and foundation on which the language was built. If it doesn’t, harmony breaks down and the result is a language that is harder to learn and to use.

Some people think D suffers from such a feature creep. To some degree I can agree. D has features that are unlikely to become widespread, but most of them are aligned towards a common goal. That goal is bringing productivity to the world of low-level programming.

Lately, a new goal has emerged from the D community, and it has triggered some real intense activity. The future of D seems to lie in the field of functional programming, making the imperative and the functional paradigms truly come together.

Why is this important? Let me quote Walter Bright from a discussion at the D forums:

The future of programming will be multicore, multithreaded. Languages that
make it easy to program them will supplant languages that don’t.
The surge in
use of Haskell and Erlang is evidence of this coming trend (the killer
feature of those languages is they make it easy to do multiprogramming).

As we all know, multithread programming in an imperative language is a real pain. It’s complicated and easy to get wrong, but that is not the case in a functional language. A pure functional program is thread-safe by design, since it’s free from mutable state and side-effects.

You never have to worry about deadlocks and race conditions because you don’t need to use locks! No piece of data in a functional program is modified twice by the same thread, let alone by two different threads. That means you can easily add threads without ever giving conventional problems that plague concurrency applications a second thought!

Quote from Slava Akhmechet’s excellent article Functional Programming For the Rest of Us.

What the people behind D want to do is to create a true functional subset of the D Programming Language, and create a safe interfacing to parts of the program that are imperative. The functional subset would enforce pure functional programming, like disallowing access to mutable global state and calls to non-pure functions. In effect that would enable you to write parts of your program that need to be thread-safe in a functional style, while using the style of programming that most of us are used to for the rest.

But, it might not stop there. Andrei Alexandrescu, who’s one of the driving forces behind the functional subset, has suggested that the enforcements inside a pure function can be relaxed to allow mutability of what he calls “automatic state,” thus allowing imperative techniques to be used as long as the mutability doesn’t leak across the function barrier. Here’s an example from Andrei’s slides on the subject:

int fun(invariant(Node) n) pure {
  int i = 42;
  if (n.value) ++i;
  int accum = 0;
  for (i = 0; i != n.value; ++i) ++accum;
  return n.value + i;

This code doesn’t look a bit functional, but the result of fun() is solely dependent on its arguments, so seen from the outside it’s pure.

Mixing pure functional and main stream imperative programming is certainly bleeding-edge. As far as I know it has never been done in any other language. But even though I’m excited, I can’t help wondering whether this is the right way to go. There’s a risk that D spreads itself too thin, and that the pure functional subset of D will be too noisy; I anticipate a heavy use of the invariant keyword for instance.

Would it be a better option to create a completely new language, say Functional D, and make D and Functional D interoperable on a binary level? At least that would battle the noise by reducing the need for explicitly expressing things like immutability, which can be taken for granted in a functional language. I also suspect that the compilers would be less difficult to implement than a compiler that has to support both styles.

But then again, I don’t know much about making compilers. I just happen to be more of a minimalist when it comes to computer languages. (As opposed to my preferences for APIs and Framworks.)

Expect more posts on this subject as I plan to delve into details next.