cdiggins.com

Surprisingly a lot of people don’t realize that an imperative statement such as “a[i] = x” can be treated like pure functional code, if our array “a” is not shared.  It is simply a question of constructing a new array from the old one. This becomes very interesting, because then we can trivially translate imperative code into functional code:

tmp = a[i]; a[i] = a[j]; a[j] = tmp;

Of course, sometime in your language you are probably going to want to share objects. As soon as you explicitly share an object, you lose the property of functional purity because you introduce side-effects (changing an object in one expressions affects other expressions). So the question is, can we reduce or eliminate sharing? The answer is that to a certain degree we can, and more than most people realize.

The first thing to realize is that many assignments to or from local variable and arguments can actually be replaced with swaps or moves. This is not so obvious if you are looking at traditional assembly or bytecode, where everything is treated extremely imperatively. But consider the following byte-code:

 ldloc1; lodconst1; add; stloc1;

This is really common code, but it can be trivially replaced with a purely functional successor function: “[succ]” that is called on the right place on the stack, using “dipN”.

Another important idea is that most copy instructions can be replaced with move instructions. A copy implies either sharing or an actual copy (which can be quite expensive). Many copy instructions result from accessing elements in an array or other collection. One technique to reduce sharing is to replace array getters and setters with a “swap_at” instruction, that swaps an item on the stack, with an item in an array. This causes objects to be moved rather than copied. This way all copy instructions occur on the stack and are explicit, using “dup”. Now our goal simply becomes to reduce the number of “dup” instructions in the code. The “dup” instruction makes an explicit copy, and is going to be expensive. Some languages desire “share” instructions which copy a handle (or pointer) to an object. In such a case we have no choice but to replace the pure object with two impure handles. All functions that operate on these objects then get polluted: the impurity propagates.

So what I plan on doing is to use “dup” to make an explicit copy of an object, and to use “share” to replace an object with two handles. e.g.

   dup : (’a -> ‘a ‘a)
   share : (’a -> handle(’a) handle(’a))

Any function that we call that uses a handle then becomes impure, but at that point what can you do. The programmer has really forced your hand and is insistent on relying on side effects.