Erlang as a Target for Imperative DSLs

It's easy to show that any imperative program can be implemented functionally. Or more specifically, that any imperative program can be translated into Erlang. That doesn't mean the functional version is better or easier to write, of course.

Take an imperative program that operates on a set of variables. Put all of those variables into a dictionary called Falafel. Make every function take Falafel as the first parameter and return a tuple of the form {NewFalafel, OtherValues}. This is the classic "pass around the state of the global world" approach, except that the topic is so dry that I amuse myself by saying Falafel instead of World. But I'll go back to the normal terminology now.

What's awkward is that every time a new version of World is created inside the same function, it needs a new name. C code like this:

color = 57;
width = 205;

can be mindlessly translated to Erlang:

World2 = dict:store(color, 57, World),
World3 = dict:store(width, 205, World2),

That's completely straightforward, yes, but manually keeping track of the current name of the world is messy. This could be written as:

dict:store(width, 205, dict:store(color, 57, World))

which has the same potential for programmer confusion when it comes to larger, general cases. I wouldn't want to write code like this by hand. But perhaps worrying about the limitations of a human programmer is misguided. It's easy enough to start with a simple imperative language and generate Erlang code from it. Or wait, is that cheating? Or admitting that functional programming can be awkward?

None of this eliminates the issue that dict:store involves a lot of Erlang code, code that's executed for every faux variable update.

A different angle is to remember that parameters in a tail call are really destructive updates (see A Deeper Look at Tail Recursion in Erlang; and I should have said "Tail Calls" instead of "Tail Recursion" when I wrote the title). Arbitrarily messy imperative code can be mechanically translated to Erlang through a simple scheme:

Keep track of the live variables. If a variable is updated, jump to a new function with all live variables passed as parameters and the updated variable replaced with its new value.

Here's some C:

total++;
count += total;
row = x * 200 + count;

And here's the Erlang version, again mindlessly translated:

code_1(X, Total, Count) ->
   code_2(X, Total + 1, Count).
code_2(X, Total, Count) ->
   code_3(X, Total, Count + Total).
code_3(X, Total, Count) ->
   code_4(X, Total, Count, X * 200 + Count).
code_4(X, Total, Count, Row) ->
   ...

Hard to read? Yes. Bulky at the source code level, too. But this is highly efficient Erlang, much faster than the dictionary version. I'd even call it optimal in terms of the BEAM virtual machine.

permalink November 18, 2007

Erlang as a Target for Imperative DSLs

previously

archives