From C++ to Scheme and back ...

I have a little confession to make. I have a thing for the Scheme programming language. After writing a post on how much I love C++, it is time to talk a little about Scheme and then immediately go back to loving C++. I was introduced to Scheme during my bachelors degree. We had to take Scheme in two main classes one of which was a Compiler's Design class. The professor who taught the class had an even bigger thing for Scheme. Heck, the guy dreamed in Scheme. I always admired his passion, but couldn't quite get what it was about it that made this language appealing.

 

Today, I can only regret not asking him more questions and digging even deeper into the language.Scheme or functional languages in general open up your mind. They require you to think differently about how you program and how you solve problems. I highly recommend the language to anyone who hasn't tried functional programming before. Once you get it ,well ... you just get it. I don't consider myself a subject matter expert, since unlike C++ I don't have as many flight hours with Scheme. However, there are certain paradigms that I have been able to grasp fairly well, and would like to share . So lets code in Scheme shall we ? lets write a small program to compute the Nth Fibonacci number:

Hey ... That Scheme language of yours looks awfully like C++ !  Weird C++, but C++.

Yea, I know. I cheated. This is C++. More specifically, C++11 with the support of std:::function and lambdas. We'll get back to this example in a short while.

By the way, did I hear someone mention lambdas? Many software engineers aren't aware of the origins of lambdas. To many, lambdas are anonymous functions that you use conveniently in C# and now in C++ as throwaway functions. So just as a recap, Lambda Calculus was developed as a mathematical formal system by Alonzo Church in the 1930th. Incidentally, they are a universal model of computation, which means in simple words that you can use lambdas (computable functions)  to compute anything that you would be able to compute with the best and most powerful (yet to be invented) supercomputer. In Lambda Calculus lambdas are first type objects, which means that they can be passed as inputs or returned as outputs from other lambdas. Functional programming languages are essentially an implementation of lambda calculus. Lisp which was developed in the 1950th at MIT is the flagship of functional programming languages. Scheme, is merely a dialect of Lisp. Now let's look at some real Scheme, and how lambdas can be used:

So why is this important?  Lambdas enable us to talk about closures and continuations. Closures refer to functions and their associated environment, or to put it simply, a data structure that is aware of the computation to be performed (the function) as well as all the data (variables) that are not local to that computation (global variables). According to Wikipedia the definition of continuations is an abstraction of the control state of a program. The way I like to put it is the computation remaining to be performed at any given time during the program's execution. what is the continuation after (Fib (- n 1)) and (Fib (- n 2)) are evaluated ? let's denote their corresponding results with X and Y. The continuation can be expressed in terms of X and Y as follows:

Continuations can be expressed very naturally using lambdas because of their semantics and behavior.

In Scheme, we can capture a continuation in a variable and pass that variable from one function to another.

Scheme also has the call/cc function which captures the current continuation when it is called.

This can enable us to pass control from one part of the program to another very simple, enabling to create exception handling and co-routines. Let see how we can define the continuation in our previous example:

This new implementation of Fib accepts a new parameter. This parameter is a lambda function that represents our continuation. We pass the results of the recursive calls to K (the continuation). The continuation is the same as we showed previously (e.g. it takes X , Y  and sums them). From this example emerges a new concept called "Continuation Passing Style".

Imagine you are writing a program in C. You have three procedures: Foobar, Goobar, and Hoobar. Foobar calls Goobar which in turn calls HooBar. Imagine that Foobar had the ability to pass to Goobar an additional parameter. This parameter includes all the computations that Foobar would have performed after Goobar returned and in addition Foobar's stack frame. Imagine that Hoobar would receive a similar parameter from Goobar. Now, when Hoobar completes its computations, instead of returning to Goobar and unwinding its stack frame, it simply uses the parameter that Goobar passed to it to perform the computations that Goobar would have made. It would apply Goodbar's computation on its own results. Similarly, Goobar would not return to Foobar and would not unwind its own stack frame. This is exactly what continuation passing style is. We pass to each function call a continuation and apply that continuation to our current result. Now imagine, that the compiler (or interpreter in the case of Scheme) had an optimization in which it would recognize that a recursive call is always made as the last thing the function does, and in this case it would not create new stack frames for the recursive calls, but instead would just override the current stack frame. This optimization exists and it is called - tail recursion optimization. However, most recursive calls are not naturally suited for tail recursion.

Take for example our Fibonacci example. We have to make two recursive calls (for the case of n - 1 and for the case of n - 2) and then sum them. But, if we could leverage continuation passing style, we could easily turn into a tail recursive structure. All we would have to do is to call one time to the recursive Fib and pass to it a continuation which corresponds to everything we would have done after it returned. Let's see the code:

  

let's examine this example carefully. As before Fib accepts two parameters, N the value to compute for and K - a continuation. when we reach the edge case of the recursion (e.g. N <= 1) we simply apply K to N. Otherwise we call Fib with N - 1 and pass to it the second continuation. This time it is a lambda(x) which inside it calls Fib (N - 2) with a third continuation which applies K to the sum of X and Y. what are these X and Y ? This is where the pieces of the puzzle come together. X and Y are the corresponding results of Fib (N - 1) and Fib (N - 2). the K that is applied to (X + Y) is a different K each time (depending on where we are in the recursive stack). However, the initial K that is passed to Fib (as can be seen with the example of N = 8) is (lambda(x) x) which is merely the identity function. In order to fully appreciate it we should show how it works for a specific case of N. For simplicity lets make it N = 3 and print the values of N X and Y throughout the calls.

Now let's see the prints for the case of N = 3:

So now finally we come back to our initial example at the beginning of this post.

If you look at it closely you will notice that it is exactly the same Fibonacci function leveraging continuation passing style in C++. Beautiful how everything falls into place.

In conclusion, I highly recommend learning a functional programming language.

If you can, learn Scheme as it is both elegant and beautiful.

But more importantly, notice how C++ lends itself nicely to functional programming concepts and how you can leverage these concepts in your day to day coding.

Comments

• Anonymous
  March 19, 2016
  continuation in c++ looks ugly.