Lately, I’ve been adding support for tail recursion optimization in the Blaise compiler. Anytime the last statement inside of the body of a function is a call to itself: it’s a tail recursive call. The execution moves from the bottom of the body of code to the top of the body of code. This works just like a loop. Normally with recursion the computer will push an environment onto stack memory and move into the new recursive function call with a free environment to which it can write local variables. With tail recursion it’s not necessary to push onto stack memory. The code can be transformed into a loop and the Blaise compiler does just that. Check out the example below.

Here is a tail recursive function

let someFunction arg1 arg2 =
    (* body of function *)
    (* The last statement is a recursive call.*)
    someFunction arg1' arg2'
;;

When the example function above is compiled to C we can use ‘goto’ statements to turn the function into a loop.

void * someFunction(void * arg1, void * arg2) {
someFunction_goto:
    /* body of function */
    /*
        The recursive call is turned into variable reassignments and
        a goto statement that takes us to the top of the loop
    */
    arg1 = arg1';
    arg2 = arg2';
    goto someFunction_goto;
}

Next I plan on adding tail recursion support for mutually (tail) recursive functions.

Sadly, this topic confused me for awhile. Recently, I found that supporting currying for unknown functions is a fairly easy concept. I didn’t realize how easy of a concept this was until I spoke with a postdoc that has experience developing functional language compilers. 🙂 At first I was perplexed by the idea that a single pass compiler was supposed to support calling a function that may not have been defined in code. That didn’t make sense and it still doesn’t make sense! One should only be able to call a function when it has already been defined!

The only time a function may have already been defined but unknown in certain parts of code is when a function requires another function as a parameter. A generic function that takes a function as an argument doesn’t know which function is going to be passed to it… therefore we have an unknown function, inside the body of function definition.

Currying for known functions in Blaise is now supported! Implementing this functionality wasn’t too hard. My largest obstacle was writing the proper OCaml syntax in the compiler. I understood the logic of my problem shortly after receiving my assignment but, since I’m not an avid functional programmer there were a few quirks in OCaml that I need to get used to.

Now I’m going to support currying for unknown functions. This will be a bit more difficult and I have to do a bit of research to figure out how to implement this feature.

Before last week I thought of curry as a delicious spice… from this point forward I will now think of a programming language feature. I’m currently adding support for currying in Blaise. A Blaise programmer can invoke a function with too few or too many arguments. Doing so causes a function to return a partial application instead of a value for a fully saturated function call. Later on the developer can invoke the partial application and pass the rest of necessary arguments to it. Wikipedia has a pretty good explanation on currying.

Here’s an example of currying with Ocaml-ish syntax:

let f arg1 arg2 arg3 =
    (* body of code *)
;;
let x = (f 1 2);;
let y = (x 3);;

Notice how the first time I invoke f I didn’t pass three arguments. x will become a partial application. Later, x, the partial application, is called with one argument – giving the function f a third argument it is invoked. The following line of code will result with y attaining the same value as the code above.

let y = (f 1 2 3);