Functional Programming – Modern C Programming

Functional Programming is getting more and more popular these days. Although this programming concept exists since the 1950's and is already present in languages like LISP, most programming languages ignored it until recently. But can you apply these concepts in the C language? You can apply many concepts of Functional Programming in the C language. The simplest concepts to implement are Pure Functions, Referential Transparency and Recursion. We will cover what exactly functional programming is and give examples of how to implement it with the C programming language in the rest of this article. Functional Programming in C Principles of Functional Programming Functional Programming is a programming paradigm. The goal is to describe the program declaratively (what it should do) as opposed to the widely used imperative programming approach (how to do it). This is achieved by applying and compiling functions. A Functional Programming Language supports and encourages this paradigm. The biggest advantage of Functional Programming is the possibility to run the code parallel because there is no mutable state. It is also very efficient because the functions can run as independent units concurrently. The main disadvantage is the large memory consumption because you have to create many objects due to the immutable states. You also have to be careful with heap space when relying heavily on recursion instead of iteration. Keep in mind that this is a very brief introduction. We will only cover enough detail in order to understand the way we can implement Functional Programming concepts in C. Disclaimer: There is more to Functional Programming than I can cover in this article alone. Please consider it as a first glimpse into the possibilities of C when it comes to Functional Programming. I will cover different aspects in other articles. Functions In Functional Programming, a function is a so-called first-class citizen. This means that a function is treated as a data type and thus can be used as variable type, function parameter and return type like any other data type. In the special case that functions take another functions as arguments or return a function, they are called higher order functions. You can see how this is implemented in C in an example below where we use functions as return values (types) and as parameter (data). There is a difference between functions (or procedures) in languages like C, Pascal, etc. and the functions in purely functional languages like Haskell. Functions in Functional Programming are pure. For a function to be considered 'pure', it must meet the following criteria: The function returns the same output for the same input every time. Therefore, no other program states or variables can alter the behaviour of the function and change the result. The function has no side-effects. A side-effect is everything that changes the state of a program (static variables, global variables, reference arguments, etc.) and input/output operations. The function add in the following example program violates both rules at the same time. It has a side-effect because it changes the sum variable and it returns different results for the same input because of this side-effect. The first call returns 3 and the second call returns 6. #include static int sum = 0; int add(int a, int b) { sum += a + b; /* Side-Effect */ return sum; } void main() { int first = add(1,2); int second = add(1,2); sum += 1; printf("%d\n", first); /* Prints: 3 */ printf("%d\n", second); /* Prints: 6 */ printf("%d\n", sum); /* Prints: 7 */ } When we convert sum into a pure function we get rid of the side-effect and also guarantee that we get the same output for the same input every time: #include static int sum = 0; int add(int a, int b) { return a + b; } void main() { int first = add(1,2); int second = add(1,2); sum += 1; printf("%d\n", first); /* Prints: 3 */ printf("%d\n", second); /* Prints: 3 */ printf("%d\n", sum); /* Prints: 1 */ } Recursion In imperative programming iteration is usually solved through loops. You declare a while or for loop and loop until a predefined condition is met. In declarative (functional) programming however this is solved through recursion. Let's look at a simple example of this. We want to add n numbers and use a for loop to do this: int get_sum_of_numbers(int count) { int sum = 0; for(int i=1;i<=count;i++) { sum += i; } return sum; } void main() { int sum = get_sum_of_numbers(5); printf("sum: %d\n", sum); /* Prints: 15 */ } We can achieve the same result by recursion: int recursive_sum_of_numbers(int count) { if(count <= 1) { return 1; } return count + recursive_sum_of_numbers(count-1); } void main() { int rec = recursive_sum_of_numbers(5); printf("rec: %d\n", rec); /* Prints: 15 */ } Lazy Evaluation In general there are two evaluation strategies for functional programming languages. Either they do strict or lazy evaluation of function arguments. In strict evaluation, every parameter is evaluated before the function itself is invoked whereas in lazy evaluation, the arguments are only evaluated if they are needed. The latter approach could make a function compile and run that carries an invalid argument. John Hughes calls this Separation of Concerns. The C Language has no Lazy Evaluation out of the box. However, you can implement some kind of mechanism your own that emulates it. If you want to get an idea of how to do it, you can find it in this blog post from Siddhart Bath. Referential Transparency Every variable in a program can be replaced by its value in any given time. This is called referential transparency and it is possible because variables can only change its value during initialization. After the initialization no assignment of a value is possible. In C we can achieve this state by making a variable const. When a variable changes its value, a new variable is created with the changed value. Often the new value is the result of a (pure) function that takes the old value as a parameter. Going back to our add function from the example above, we see what happens to sum in the course of the program. It first is 3 but later it changes to 7 and if this change is not noticed by the programmer, he could get in trouble. int add(int a, int b) { return a + b; } void main() { int sum = add(1,2); /* sum is now 3 */ /* ....................... */ /* Maaaaany lines of code */ /* ....................... */ sum = add(sum,4); /* sum is now 7 */ } Making sum a const prevents this, ensures referential transparency and forces the programmer to use another variable. We could replace sum with 3 now everywhere in the code. int add(int a, int b) { return a + b; } void main() { const int sum = add(1,2); /* sum is now 3 */ /* ....................... */ /* Maaaaany lines of code */ /* ....................... */ /* sum = add(sum,4); This would not compile now!! */ int anotherSum = add(sum, 4); /* Achieves the same result */ } Lambda Calculus If you start to deal with functional programming, sooner or later you will come across the term Lambda Calculus. Wikipedia says: Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. Wikipedia, visited in November 2022 If you are still not smarter, the following description might help you: [The Lambda Calculus is a] Fancy name for rules about how to represent and evaluate expressions with unnamed functions. Stephen A. Edwards, Functional Programming and the Lambda Calculus A Lambda Function is guaranteed to have no side effects. C++ offers this mechanism since C++ 11, in the C Language we are out of luck again. Like Lazy Evaluation this mechanism of Functional Programming is missing and you have to implement it on your own. Unfortunately this time you can only emulate this behaviour with non-standard language features and therefore have to rely on specific compilers like in the examples here and here. I/O Manipulation with Monads By what we have learnt so far, in functional programming there is no changing of variables or state, or any other mutation. But as good as a program may be, if there is no input or at least some kind of output, what use is it then? In pure functional languages the solution are so called Monads. There are different types of Monads and the ones for input and output operations are called I/O Monads. They essentially abstract the side-effects away. The definition and deep explanation would go beyond the scope of this post. Wikipedia does this, as well as the Haskell Documentaion and this very good answer at Stack Overflow. The Maybe Monad One Monad that exists in many languages is the Maybe Monad, though it may have different names. Instead of returning NULL if something was not found (a thing you should never do), you will return Empty or Nothing and otherwise just return the value. The following is an example of a MaybeInt type which either returns an int or nothing: typedef struct maybe_int_t { int just; int nothing; } maybe_int_t; const maybe_int_t Nothing = (maybe_int_t) { .nothing = 1 }; maybe_int_t returnMaybe(int x) { return (maybe_int_t) { .just = x, .nothing = 0}; } maybe_int_t testFunction(int x) { return (x < 1) ? Nothing : returnMaybe(x - 3); } This may be not complete and implementations may differ. Just consider it as a starting point for your own Maybe implementation. Functional Programming in C Before we finally dive into an example of how to do Functional Programming in C, I would like to refer to the Book Functional Programming in C++, by Ivan Čukić. The subtitle of this book is How to improve your C++ programs using functional techniques and this perfectly describes what we want to do here in C, too. The book is great but Ivan has an "unfair" advantage: Newer C++ Versions (since C++11, and even more in C++14 and C++17) do have a lot of built-in functionality that support the Functional Programming style. This is, by the way, another sign of the success of this programming philosophy. But now we will focus on our good old C code and how to implement the principles of Functional Programming. Example: A Finite State Machine The following is a very simple Finite State Machine (FSM) that represents a very simple Game Loop. You wouldn't want to have it this simple in a real game, but it may be suffice for the sake of this example. A very simple Finite State Machine representing Game States The transition table shows that we only have three transitions to care about. We also have four states that our game can be in. Current Game StateTransitionNew Game StateGAME_INITLoadingGAME_MENUGAME_MENUPlayingGAME_RUNNINGGAME_RUNNINGGame QuitGAME_EXITGAME_EXIT//A Simple Transition Table for our Finite State Machine The Imperative Game Loop in C In "traditional" C, a programmer would come up with something like the following code. It's an imperative implementation of the state machine, defining the game state as enum, running the game loop in an infinite while loop and checking for transitions in a big switch case. #include typedef enum game_state_t { GAME_INIT, GAME_MENU, GAME_RUNNING, GAME_EXIT } game_state_t; char* game_state_string[4] = {"GAME_INIT", "GAME_MENU", "GAME_RUNNING", "GAME_EXIT"}; static int game_state = GAME_INIT; static int is_game_running = 1; static int menu_delay = 3; static int game_delay = 5; void game_state_machine( void ); void main() { while(is_game_running) { printf("Current Game State: %s\n", game_state_string[game_state]); game_state_machine(); } } void game_state_machine( void ) { switch (game_state) { case GAME_INIT: game_state = GAME_MENU; break; case GAME_MENU: if(menu_delay<=0) { game_state = GAME_RUNNING; } else { menu_delay--; } break; case GAME_RUNNING: if(game_delay <= 0) { game_state = GAME_EXIT; } else { game_delay--; } break; case GAME_EXIT: is_game_running = 0; break; default: /* This should never happen*/ break; } } With regard to functional programming, here are some points that do not correspond to the paradigm: A While-Loop Several variables that change state The functions have side-effects A switch-case is used There are unreflected output operations We also have an ugly comment on a branch that should never happen anyway The Functional Game Loop in C Now we re-write the program and take care of the non-functional points that were pointed out above. We keep the game state enum and its string representation as well as the constants for our delays. First we abstract away the output to the console. This is only semi-functional as we will not return any value, but for this simple example it will at least encapsulate this of side-effect. void console_output(const game_state_t current_state) { printf("Current Functional Game State: %s\n", game_state_string[current_state]); } Next we replace the infinite while loop with recursion. We call the transition_to function with the current state and re-call the functional_game_loop with the new state. The exit condition is when transition_to returns GAME_EXIT. This way we don't have a while loop or any variable mutations. Please note that we use a function as data (parameter) here. void functional_game_loop(const game_state_t next_state) { console_output(next_state); if(next_state==GAME_EXIT) { return; } functional_game_loop(transition_to(next_state)); } In order to get rid of the switch-case and the other variable mutations, we introduce an array that contains pointer to functions that handle the actions in any given game state: typedef game_state_t (*game_action)(); /* for convenience */ game_state_t loading_handler(void); game_state_t playing_handler(void); game_state_t quitting_handler(void); game_action const transition_table[MAX_STATE] = { &loading_handler, &playing_handler, &quitting_handler }; The transition_to function now calls the corresponding function via it's pointer. const game_state_t transition_to(const game_state_t game_state) { return transition_table[game_state](); } This is the complete code of our game loop, but now with the functional modifications. The execution leads to exactly the same result as above. #include /** TYPES **/ typedef enum game_state_t { GAME_INIT, GAME_MENU, GAME_RUNNING, GAME_EXIT, /* ... */ MAX_STATE } game_state_t; typedef game_state_t (*game_action)(); /** PROTOTYPES **/ game_state_t loading_handler(void); game_state_t playing_handler(void); game_state_t quitting_handler(void); void functional_game_loop(const game_state_t next_state) /** VARIABLES **/ char* game_state_string[4] = {"GAME_INIT", "GAME_MENU", "GAME_RUNNING", "GAME_EXIT"}; static int menu_delay = 3; static int game_delay = 5; game_action const transition_table[MAX_STATE] = { &loading_handler, &playing_handler, &quitting_handler }; /** MAIN **/ void main() { functional_game_loop(GAME_INIT); } /** FUNCTIONS **/ void console_output(const game_state_t current_state) { printf("Current Functional Game State: %s\n", game_state_string[current_state]); } void delay(const int times, const game_state_t current_game_state) { if(times <= 0) { return; } console_output(current_game_state); delay((times - 1), current_game_state); } game_state_t loading_handler(void) { return GAME_MENU; } game_state_t playing_handler(void) { delay(menu_delay, GAME_MENU); return GAME_RUNNING; } game_state_t quitting_handler(void) { delay(game_delay, GAME_RUNNING); return GAME_EXIT; } const game_state_t transition_to(const game_state_t game_state) { return transition_table[game_state](); } void functional_game_loop(const game_state_t next_state) { console_output(next_state); if(next_state==GAME_EXIT) { return; } functional_game_loop(transition_to(next_state)); } Key Takeaways C isn't a Functional Programming language by default You can implement functional concepts in C and thus get some of the benefits Some concepts are difficult to implement, if at all, such as lazy evaluation This article was first published by Marco Lieblang on moderncprogramming.com. If you are reading this somewhere else, it may be plagiarism.