Functional Programming in C
Or how to make the most of a CS Master while handling mundane tasks
I was not sure about how to title this article: on one hand, functional programming in C is undoubtedly what I’m trying to do here; on the other, depending on your definition of functional programming the results might sorely disappoint. In the end, this is a showcase on how to use an academic and functional mindset while working with a low-level, scarce programming language such as C. It is also a very, very simple example, so don’t expect any major breakthrough in your mindset after reading it.
My job rotates around low level C programming for custom embedded platforms, and I love it; still, initializing screen controllers and flipping output ports after a fixed delay is not the highlight of my day. It involves a lot of boring and unrewarding code without many options for improvement.
Last week I was working on an embedded PIC device, a simple timer control with some GUI sparkles on a 128x64 monochrome display. Specifically, I needed to manage concurrently a couple of timers: the user sets a 1 minute delay, starts it, a relay clicks and a light is left on for 60 seconds before shutting off again. Hurray.
Nonetheless, as my Master in Computer Science draws to an end, I felt especially inspired to make the best out of my preparation.
What I was instructed to do in this situation by my self-taught co-worker was to create a counter variable and decrement it in an interrupt timer, just like this:
unsigned long delay;/* 1 second repeating interrupt */
void timer_interrupt() {
if (delay > 0)
delay--;
}void main() {
init_interrupts();
counter = 10;
while(counter > 0) {
// Timer is ticking...
}
// Timer is done
}
It’s trivial and it works, but you shouldn’t do that. First of all, it’s not architecturally portable: not every platform will manage timer interrupts in the same way (if there are at all). Hell, it’s not even portable on the same machine: every time you need a new timer a new variable must be created and separately decremented!
Second, exposed global variables. Don’t do that.
For a while I’ve worked this way, but last week I was comfortable enough to change, so I started practicing what I had been taught in University. First rule of programming: do not re-invent the wheel. Timers are a fairly common tool, surely someone must have created something already, right?
Obviously, yes. I googled “embedded timer library” and found a Github repo matching the description. The functionality is all there, with the possibility to create a timer and inquire whether it expired or not; good! How can I integrate it in my project? What are the dependencies? Just two:
- Dynamic memory allocation
- A function that returns the current time
I frowned. Not much, but too much nonetheless. I’m working on a very small 16-bits PIC: nothing in my firmware requires dynamic memory and I’d rather keep it that way. Also, I have to initialize the library with a pointer to a function returning the current time. What current time? Seconds? Microseconds? Nanoseconds? The library has separate routines to set different grains of delay, but my system only has a 20 milliseconds interrupt… And I can’t be bothered to look up in the code what time formats the initialization actually expects.
The first problem can be solved easily, just allocate a static array of timers and use that instead of dynamic structures. I still need to connect a time-yielding callback for the library to know when timers are expired.
However, as trivial as the procedure might be, timers should be simpler than that. Does it really have to be this hard to include a generic implementation? The answer — the one I’ve found at least — is a resounding no. You can indeed have a zero-dependency implementation for timers, one that doesn’t even need time.
In that same period I was studying Haskell, functional programming and Monads. In particular, I was beginning to wrap my head around the IO Monad and how it defeats the need for side effects (no need to understand that to keep reading — I’m not yet sure I do either).
C offers little tools for functional programming: there are no anonymous functions (lambdas), no first-order functions, recursion is possible but not advised without a tail-recursive mechanism. However, one might argue that true functional programming is not about that as much as avoiding side effects by using only pure, mathematical functions, and that can be achieved with any programming language.
Here the challenge gets interesting, because timers are a quintessential example of impure objects: the same function to check if the delay is finished will, by definition, yield different results over multiple calls despite having the same arguments. A clock has an internal state and evolves regardless of your interface to it. So how do you stop time?
Imagine you’re doing the work of the timer library. You are given a delay in seconds and asked to keep track of it — any arbitrary delay, from 10 seconds to 2 hours. The first thing any sensible person would ask for is a functioning clock.
But I’m on a very short budget, and I’m not going to give you a clock; I do have one on my wrist but I can’t be bothered to take it off. Still, I give you a 15 minutes delay and tell you I’ll come back to check if it has passed or not. What would you say?
“Well, at least tell me what time it is”.
That’s the key to the problem. You can keep track of time without a clock as long as you are told the time when consulted. If I reveal the timer starts at 13.00 you will know whether it has expired when I come back saying it’s 13.14.
I know this sounds redundant (of course I don’t need to check the time if I know the time, duh), but it actually makes a lot of sense if you think about it hard enough. In a way, it is the same path Haskell takes with IO Monads: side effects emerge when there is an hidden state that changes under the hood; to remove them I’m just going to uncover the real world and pass it as an argument to my now pure function.
My timer library does not need to include a ticking clock as long as I pass the current time along with every function call. Does this sound cumbersome to you? Not any more than keeping track of an internal time anyway.
With this great revelation in mind I created my own embedded timer library. The implementation itself is very simple, just a matter of subtraction between the current timestamp and the saved starting moment, with some clutter to handle pausing and restarting.
Every function is perfectly pure and the integration is seamless: just two files, generic_timer.c and generic_timer.h that require 0 connections to outside facilities. They can be used everywhere, from Linux to Embedded.
For example, the start_timer function takes two parameters: a timer and the current time. It stores the current time inside the timer and returns. When I query the state with is_timer_reached I need to pass the current time again: a difference between the latter and the starting timestamp quickly tells me how many units have elapsed with the corresponding answer. It’s basically just a glorified math library!
Abstracting completely the passage of time has a second added benefit: all timers are independent from units of measure. You want to count seconds? Just pass the time in seconds. Need a finer grain? I don’t need to know about that as long as you can count in smaller time units. Almost every function has a currenttime argument that you can build however you want — the implementation doesn’t care as long as it’s a growing number.
A typical usage looks like this:
// Start the timer somewhere
timer = create_timer();
set_timer(timer, 120); // two minutes
start_timer(timer, get_seconds());while (work) {
// Other operations ... if (get_timer_state(timer) == TIMER_PAUSED) {
memset(string, ' ', 5);
string[5] = '\0';
} else if (is_timer_reached(timer, get_seconds())) {
stop_timer(timer);
clear_digout_all();
sprintf(string, "%02d:%02d", 0, 0);
} else {
time = get_time_left(timer, get_seconds());
minutes = time / 60;
seconds = time % 60;
sprintf(string, "%02d:%02d", minutes, seconds);
}// Display the string ...
}
Conclusion
All in all, I’m very satisfied with the result. I’ve proven to myself that I can apply the functional approach even to a desert environment like embedded C; it’s all about the mathematical mindset. I’ll surely use my newly built library in all my future projects.
This kind of solutions help me kill time while I wait to try out modern languages like Lua or Rust on microcontrollers.
Note:
previously I said that every function is perfectly pure; this is not entirely true. In my implementation timer handlers generic_timer_t are just a typedef for timer structure pointers. This means, technically, that a function call with the same arguments (say, an address that points to the same structure used again after destroying a previous timer) can yield different results. To have a properly pure function I should pass the entire timer structure with all the containing data instead of an arbitrary handle type.
However, I argue that there is little conceptual difference between using a handle of that sort and the real data. Even Haskell passes around references for its objects instead of an actual copy, but since the implementation is obscured to the developer (as is the generic_timer_t ), the function is considered pure nonetheless.
Ultimately, I just want to avoid passing around sizable data copies and to expose the internal structure of a timer.
