Kalium

Kalium is a research project. The goal is to generate idiomatic functional code from imperative code. The source language is Pascal (because it's easy to implement), and the target language is Haskell (because it's powerful).

The translator itself is written in Haskell and hosted on GitHub. Contributions are welcome, so feel free to open an issue or create a pull request.

Why bother?

There are reasons to believe that functional paradigm is superior. The incomplete list being:

• Code becomes more concise and flexible—thanks to higher order functions.
• Strong static typing helps to prevent bugs, but doesn't get in the way.
• The lack of implicit state means that code is way eaiser to reason about and maintain.
• Procedural/object-oriented concepts are embeddable using modern techniques (state monad, lenses).
• Parallel and concurrent algorithms are way easier to implement.

Yet there's an unresolved question: what do we do with the existing codebase? Billions of lines of code are written in imperative languages. Manually rewriting every library is extremely tedious and can introduce new bugs.

The problem

Functional programming is based on λ-calculus, whereas imperative programming takes Turing-machine model as its basis. But these are equivalent—for every program there's a direct translation from one model to another.

The actual problem is not the translation itself, but preserving the higher-order abstractions. And this is really difficult (probably impossible) to accomplish, as those abstractions live inside the programmer's head, not in the code. However, the code contains various reflections of those abstractions (such as functions and data types), so there should be a way to extract some information and use it to translate the program.

The solution

There's no obvious solution for this problem. Kalium aims to discover how far we can get. The core idea is pattern recognition. Numerous application of semantics-preserving transformations to the code can yield certain patterns, from which it is possible to extract high-level concepts.

The current roadmap is:

1. Translate a simple imperative language to a functional language. The output code may not be beautiful/idiomatic.
2. Find the ways to recover the initial quality of the input code, so the output is at least as good as the input.
3. Discover the possibilities to make the resulting code better than original (e.g. automatic parallelization).

Example

Kalium is far from its goal, but let's see what it currently can do. Cluttered imperative mess turns into a short and simple functional program:

function f(a: LongInt): LongInt;
var
    i: Integer;
begin
    f := 0;
    for i := 1 to a do begin
        f := f;
        f := f + i;
    end;
end;

var
    k: LongInt;
    trash: Boolean;
    i, n: Integer;
begin
    ReadLn(n);
    k := 1;
    trash := True;
    for i := 1 to n do begin
        k := k * i;
    end;
    k := f(k);
    WriteLn(k);
end.

main :: IO ()
main
  = do n <- readLn
       print (f (product [1 .. n]))

f :: Int -> Int
f a = sum [1 .. a]

Can I help?

Sure! Fork the repo and do whatever you think is good, then create a pull request. If you don't know what to do—my email address can be found in commits—feel free to contact me.

Another way to contribute is to use Kalium and find its bugs, file feature requests, etc. These may come in handy:

• Building instructions
• Supported Pascal subset (PDF)
• Tests (example programs)