Lambda the Ultimate

Does anybody know any work done on conversion of 'functional' to 'imperative' algorithms?

I am asking this because, while doing some mental exercises with algorithms to help me understand functional programming better, I realized that any functional algorithm could be converted to an imperative one, in order to save resources and increase performance.

The way I work goes like this: i write down a functional algorithm, then try to optimize it by converting it to an imperative one using assigments. I try to re-use memory space, so as that the algorithm becomes faster, without loosing the meaning (and maybe correctness) of the functional algorithm.

Let me give you an example. Let's just say we have the following simple function:

let f(x) = x + 1

which is used here:

let g(y) 
with
    let a = f(y)
=
    a + 2    

We can see that the above is equal to (assignment is operator ':='; operator ',' is used for sequence of operations):

let g(y) = 
    y := y + 1,    (* reuse variable 'y' *)
    y + 2

In the above example, the variable 'y' is re-used (I am talking about variables here, not value bindings, because I am talking about implementation): instead of using an intermediate variable 'a', the compiler reuses the variable 'y', increases it by 1, then adds '2' to it and returns the result.

Of course the above example is trivial and the relevant optimization may already take place in modern FP compilers. But what about more complex examples? For example, I was thinking about the 'quicksort' algorithm. The functional algorithm goes like this (in a imaginative mixture of functional and imperative syntax, using 'h:t' for head-tail list representation):

(* input is a list with first element as 'head' and the rest of elements as 'tail' *)
let qsort(head:tail)
with
    (* less and greater than nil is nil *)
    let less(e, nil) = nil
    let greater(e, nil) = nil
    
    (* calculate elements of input list 'h:t' less than 'e' *)
    let less(e, h:t) = 
        (if h < e then h else nil) + 
        less(e, t)
        
    (* calculate elements of input list 'h:t' greater than 'e' *)
    let greater(e, h:t) = 
        (if h > e then h else nil) + 
        greater(e, t)
=
    (* the result is: less elements + head + greater elements *)
    qsort(less(head, tail)) + 
    head + 
    qsort(greater(head, tail))

The actual implementation of the algorithm is quite slow, since it copies data around in a new list for each 'invocation' (I am not talking 'reduction' here, because I speak about actual code running on a computer). The ideal would be if the above functional algorithm could be converted automatically to an imperative one that does in-place sorting.

If we examine closely the above quicksort algorithm, we will see that the algorithm does the following things:

1. get all the elements of the list less than its 'first element' into a 'list A'.
2. get all the elements of the list greater than its 'first element' into a 'list B'.
3. sort 'list A'.
4. sort 'list B'.
5. the end result is 'list A' + 'first element' + 'list B'.

Let's see if we can speed up the above algorithm (let's name it quicksort A) by using two lists: a list A which is the input list and a list B which is the output list. Instead of creating new lists, we are going to use list B as an intermediate list for sorting elements, without changing the basic logic behind the sorting algorithm.

The 'less' function can be written like this:

let less(e, ha:ta, out hb:tb) =     
    if ha < e then        
        hb := ha,            (* copy value of element 'ha' to 'hb' *)                        
        less(e, ta, tb)      (* process rest of elements of A into tail of B *)
    else     
        less(e, ta, hb:tb)   (* process rest of elements of A into B *)

The above algorithm uses another list B to accumulate the 'less than first element' data of a list. The 'greater' algorithm can be written in the same way.

Now the qsort algorithm becomes:

(* input is list 'ha:ta', output is list B, which must have the same length as 'ha:ta' *)
let qsort(ha:ta, out B)
with
    let temp = List(sizeof(ha:ta))     (* temp is a list with same size as list 'ha:ta' *)
=
    less(ha, ta, temp),                (* accumulate elements of 'ta' less than 'ha' into 'temp' *)     
    qsort(temp, B),                    (* sort temp list into B *)
    B[sizeof(temp)] := ha,             (* copy 'ha' right after 'temp' sorted into B *)
    greater(ha, ta, temp),             (* accumulate elements of 'ta' greater than 'ta' into 'temp' *) 
    qsort(temp, B + sizeof(temp) + 1)  (* sort temp list into B right after the less part and the 'ha' element *) 

The above algorithm (let's name it quicksort B) can be preferrable than the pure one, because the intermediate variable 'temp' can exist on the stack, thus increasing performance of the program and reducing garbage (or be used for compile-time garbage collection). Here is a working C++ implementation:

#include 
using namespace std;

#define ARRAY_SIZE      5

int less(int e, const int in[], int in_size, int out[])
{
    int c = 0;
    for(int i = 0; i < in_size; ++i) {
        if (in[i] < e) {
            out[c] = in[i];
            ++c;
        }
    }
    return c;
}

int greater(int e, const int in[], int in_size, int out[])
{
    int c = 0;
    for(int i = 0; i < in_size; ++i) {
        if (in[i] > e) {
            out[c] = in[i];
            ++c;
        }
    }
    return c;
}

void sort(const int in[], int in_size, int out[])
{
    if (in_size == 0) return;
    int temp[ARRAY_SIZE];
    int c = less(in[0], in + 1, in_size - 1, temp);
    sort(temp, c, out);
    out[c] = in[0];
    int c1 = greater(in[0], in + 1, in_size - 1, temp);
    sort(temp, c1, out + c + 1);
}

void sort(const int in[ARRAY_SIZE], int out[ARRAY_SIZE])
{
    sort(in, ARRAY_SIZE, out);
}

int main(int argc, char* argv[])
{
    int in[ARRAY_SIZE] = {5, 6, 7, 3, 8};
    int out[ARRAY_SIZE];

    sort(in, out);

    for(int i = 0; i < ARRAY_SIZE; i++) {
        cout << out[i] << endl;
    }

    getchar();
    return 0;
}

Is it possible to optimize the algorithm further? could the sorting be done without using a second list? The answer is yes. Let's examine the 'logic' behind the sorting again: we traverse a list twice, once for accumulating the elements 'less' than an element and once for accumulating the elements 'greater' than that element. In order to do the 'less' algorithm 'in-place', we have to 'push' elements less than an element in front of the list while pushing greater elements at the end of the list. The algorithm could be like this:

(* pushes elements of 'h:t' less than 'e' at beginning of list; 
   function greater is not needed, because all the elements after the 'less' part
   automatically belong to 'greater' part
 *)
let less(e, out h:t, out f, out l) =
    if h < e then            (* less element is found *)
        l := f,              (* save value of 'f' into position 'l' *)
        f := h,              (* place less element 'h' at beginning of list *)
        f = next(f),         (* set 'f' to next position in list *)
        l = h,               (* note down the 'free' position *)
        less(e, t, f, l)     (* process the rest of elements of 't' *)
    else
        less(e, t, f, l)     (* less element is not found *)
        
(* quick sort *)        
let qsort(h:t)
with
    let f = h                (* 'f' is the first free entry in the list *)
    let l = h                (* 'l' is the last freed entry in the list *)
= 
    less(h, t, f, l),        (* push less than 'h' elements to beginning of 't' *)
    l := f,                  (* before setting middle element, save the value at middle element position *)
    f := h,                  (* set middle element *)
    qsort(t[begin..f]),      (* sort less part *)
    qsort(t[f+1..end])       (* sort greater part *)
        

Here is the working C++ implementation (let's call this version 'quicksort C'):

#include 
using namespace std;

#define ARRAY_SIZE      5

int less(int e, int a[], int begin, int end, int &f)
{
    int l = f;
    for(int i = begin; i < end; ++i) {
        if (a[i] < e) {
            a[l] = a[f];
            a[f] = a[i];
            l = i;
            ++f;
        }
    }
    return l;
}

void sort(int a[], int begin, int end)
{
    if (end <= begin) return;
    int e = a[begin];
    int c = begin;
    int l = less(e, a, begin + 1, end, c);
    a[l] = a[c];
    a[c] = e;
    sort(a, begin, c);
    sort(a, c + 1, end);
}

void sort(int a[ARRAY_SIZE])
{
    sort(a, 0, ARRAY_SIZE);
}

int main(int argc, char* argv[])
{
    int a[ARRAY_SIZE] = {5, 6, 7, 3, 8};
    
    sort(a);
    
    for(int i = 0; i < ARRAY_SIZE; i++) {
        cout << a[i] << endl;
    }
    
    getchar();
    return 0;
}

After doing all the above, I realized that I converted the purely functional quicksort A to imperative algorithm quicksort B, and then took that algorithm and convert it to quicksort C, by doing some replacements and adjusting the algorithm for overwriting data. The quicksort C algorithm is quite similar to the known partitioning algorithm (if not the same?). I have come to suspect that:

• such a conversion from 'purely functional' to 'imperative' algorithms could be formalized for any algorithm; then the compiler could handle assignments by automatically recognizing what can be reused and what can't
• all assignments in an imperative algorithm are optimizations of the relevant 'pure' algorithm(s)

Since there is no formal way of converting a functional algorithm to an imperative one, programming languages put the burden of assignment on the programmer, thus allowing for assignment-related bugs to creep in an application; the actual problem with assignments is that a programmer can easily forget when an assignment affects another part of a program. If a compiler could convert a functional algorithm to an imperative one so as that the least possible amount of resources is spent (least copying / least garbage), then functional programming languages could easily reach imperative languages' performance, while keeping their 'pure' properties.

I searched the web but I did not find a relevant paper. Does anybody know anything about this? I apologise if this is something stupid or if I did some stupid mistake or already proven not feasible, but my interest is great on this subject.