DEV Community: Michele Lindroos

What is Metaprogramming?

Michele Lindroos — Sun, 12 Jun 2022 13:57:47 +0000

Already in my teenage years as a junior programmer I heard lots of talk about Metaprogramming. Even though wikipedia didn't exist and information on the internet in general wasn't available to the same extent it is today, it was easy to look up the definition of metaprogramming. My problem was that the definition didn't tell me much. Over the years I've learned a lot more about metaprogramming. In this blog post I'll explain what metaprogramming is. Furthermore, I'll show various examples of metaprogramming.

The Definition of Metaprogramming

Now, what is metaprogramming? When we're programming, i.e. write program code, we're writing code for the program. Conversely, when we're metaprogramming, we are writing code for the code itself.

Sounds confusing? Guess how confused I was when I was 14yo and trying to learn all of this by myself...

Examples often help alleviate confusion. Hence, I will give lots of examples throughout this post. Let's start with an example in pseudocode.

Let's say we want to print the numbers from 1 to 10. Even a novice developer would think of using a loop:

for i = 1 to 10:
    print(i)

But would it be the same if we would write all the print statements out?

print(1)
print(2)
print(3)
print(4)
print(5)
print(6)
print(7)
print(8)
print(9)
print(10)

This question is more involved than first meets the eye. However, as compiler optimizations and instruction set architectures (ISA) are out-of-scope for this post, let's keep things simple and assume they will be executed as written. I.e. the former has more compact code, but the latter runs faster as it has no comparisons nor branches. A typical tradeoff between size and speed.

However, code readability is useful, too. So, what if, we would like to write the former, but end up with the code from the latter? This is something metaprogramming could solve. For example, our pseudocode with metaprogramming might look as follows:

META_FOR(i, 1, 10):
    print(i)

In our pseudocode language this would generate the 10 sequential print-statements in code.

Now that we have given the definition for metaprogramming and looked at an unrealistically simple example, let's look at some real examples.

C Preprocessor Directives

Many aspiring C programmers may not realize this at first, but the C preprocessor directives, such as #include and #define are metaprogramming. The C preprocessor, often abbreviated CPP, runs before the C compiler executes.

The GNU C compiler (GCC) ships with the C preprocessor bundled. To run only the preprocessor, without running the compiler, we have to invoke gcc with -E.

As a simple example, let's define a variable VARIABLE_X as 5 and use a print statement to print it. The code might look as follows:

$ cat define-x.c
#define VARIABLE_X 5
printf("X = %d\n", VARIABLE_X);

Now, let's run the preprocessor and see the output. (We will have to use the switch -P to avoid clutter caused by line markers the preprocessor would add by default):

$ gcc -E -P define-x.c
printf("X = %d\n", 5);

The C preprocessor supports conditionals. We can write code that will end up different depending on definitions. For example, we could use #ifdef to generate something when OS_WINDOWS is defined and something else when OS_LINUX is defined. Note that we need to end the conditional with #endif.

$ cat ifdef-windows-linux.c
#ifdef OS_WINDOWS
printf("hello Bill\n");
#endif
#ifdef OS_LINUX
printf("hello Linus\n");
#endif

Now, if we don't set either, the generated code is empty:

$ gcc -E -P ifdef-windows-linux.c

If we define OS_WINDOWS, we get as follows:

$ gcc -E -P -D OS_WINDOWS ifdef-windows-linux.c
printf("hello Bill\n");

and with OS_LINUX:

$ gcc -E -P -D OS_LINUX ifdef-windows-linux.c
printf("hello Linus\n");

We can do mathematical statements in #if's:

$ cat if-math.c
#if (6 * 7) == 42
printf("all good\n");
#else
printf("is math broken?\n");
#endif

The output is as expected:

$ gcc -E -P if-math.c
printf("all good\n");

In fact, the C preprocessor is very powerful. It is possible to do functions, loops and so forth. Now, it is important to understand that just because it is possible it doesn't mean it's a good idea. Some programs such as the linux kernel make heavy use of the C preprocessor, but most programs are best of with minimal use of it. Granted, you can't do much without #include statements and header files need include guards, but otherwise I recommend using the C preprocessor sparingly.

C++ Templates

C++ is a superset of C and therefore all of the C preprocessor macros work for C++, too. (Technically, the C preprocessor doesn't care about the source code at all and you could use the C preprocessor for whatever language you like)

In addition to the C preprocessor, C++ has templates. Unlike the C preprocessor, the C++ templates are a native construct of the language. Despite this, the C++ templates are metaprogramming. C++ templates generate code that is to be compiled.

Let's say we want to create a function that returns the sum of two integers. However, for whatever reason, we don't want to create a parameterized function taking to integers, but rather hard-code it as follows:

int sum23()
{
    return 2 + 3;
}

Now, if we want to create many of these functions, we will have to write a lot of code. Instead, we could use templates to have the compiler create the code for us:

template<int N, int M>
int template_sum()
{
    return N + M;
}

To get an instance of the function sum23(), we would do like:

int (*sum23)() = template_sum<2,3>();

Note that preferrably we would do

auto sum23 = template_sum<2,3>();

but I wanted to make the type explicit here for maximum readability.

The most common usage of C++ template is containers. Say, you want to create a linked list container. In C++, without any kind of metaprogramming, i.e. without templates and the C preprocessor, you would have to rewrite the same container for every class you want it to support. In practice, would end up copy-pasting a lot of code which is suboptimal, to say the least.

The declaration of our linked list implementation might look as follows:

template<class T>
class linked_list;

The implementation of the linked-list is out-of-scope for this post. However, assuming we would create the implementation, then, we could create linked lists with integers, string etc.

linked_list<int> my_integer_list;
linked_list<std::string> my_string_list;

Note that the templates create an equivalent of source code that has been copy-pasted, i.e. there are separate classes for linked_list<int>, linked_list<std::string> etc. for everything that is instantiated anywhere. Furthermore, as compilation units, i.e. source code object files, are compiled separately, this can grow compilation times significantly. There are some optimizations to this, but those are out-of-scope for this post.

While the C++ templates are extremely powerful, I would recommend using them sparingly. Myself, I make heavy use of the standard library containers as they're very good, but I rarely write any templates myself. Bugs related to templates are typically hard to solve. This is primarily because the compiler may not know if the bug is in the template code or in the usage of the template as either one could be the culprit.

Function Redefinition

In a language like C, declaring a function assigns the symbol used to address the function. Every further declaration of the function needs to have the same prototype or otherwise the compiler complains. For example, let's say we declare int my_sum(int, int) and later int my_sum(char, char):

$ cat my_sum.h
#pragma once
int my_sum(int a, int b);
int my_sum(char a, char b);

The compiler throws an error as expected:

$ gcc my_sum.c
In file included from my_sum.c:1:
my_sum.h:3:5: error: conflicting types for ‘my_sum’
    3 | int my_sum(char a, char b);
      |     ^~~~~~
my_sum.h:2:5: note: previous declaration of ‘my_sum’ was here
    2 | int my_sum(int a, int b);
      |     ^~~~~~

This makes sense. We want all our calls to my_sum() to be unambiguous. More important, in a language like C, functions cannot be redefined. Even if we write the exact same implementation twice, as follows:

$ cat my_sum.c
#include "my_sum.h"

int my_sum(int a, int b)
{
    return a + b;
}

int my_sum(int a, int b)
{
    return a + b;
}

the compiler throws an error:

$ gcc my_sum.c
my_sum.c:8:5: error: redefinition of ‘my_sum’
    8 | int my_sum(int a, int b)
      |     ^~~~~~
my_sum.c:3:5: note: previous definition of ‘my_sum’ was here
    3 | int my_sum(int a, int b)
      |     ^~~~~~

However, while this helps avoid confusion, it wouldn't have to be like this. Instead of functions, let's consider normal variables in C. Let's assume we declare the integer a and initially set it to 5. Later, we can set it to 7 and that is totally allowed. Essentially, we are redefining variables:

$ cat int_a.c 
#include <assert.h>
int main(void)
{
    int a = 5;
    assert(a == 5);
    a = 7;
    assert(a == 5);

    return 0;
}

Compiling and running this fails as expected:

$ gcc int_a.c && ./a.out 
a.out: int_a.c:7: main: Assertion `a == 5' failed.
Aborted (core dumped)

If we change the latter assertion to a == 7, the code runs fine.

Why is it that we can redefine variables, but not functions? Are not the names we used to address functions not symbols just like the variables are?

Indeed, and in many languages, such as python and javascript, function redefinition is perfectly allowed.

Javascript Function Redefinition

Let's talk about javascript. Let's assume we want to write a function my_greeting() which returns a string containing a greeting message. For example, let's make the implementation as follows:

function my_greeting() {
    return 'hello';
}

Now, if we call the function and use the result as input for console.log(), the expected message is printed:

> console.log(my_greeting());
hello

Unlike in a language like C, we can redefine the function at will. Let's say we feel a little Spanish and want to change greeting accordingly:

function my_greeting() {
    return 'hola que tal';
}

Now, if we use the same code as before, it will call the new implementation:

> console.log(my_greeting());
hola que tal

Not only can we redefine standalone functions. We can also redefine functions belonging to an object. Let's say we have a class Banana which has a function getColor() which returns 'green':

class Banana {
    getColor() {
        return 'green';
    }
}

Instantiating this class and calling getColor() returns the expected result:

> my_banana = new Banana();
Banana {}
> my_banana.getColor();
'green'

Now, we can change the implementation of the function. If we want to change the implementation of the single instance of the class, we can do as follows:

> my_banana.getColor = function() { return 'yellow'; }
[Function]
> my_banana.getColor();
'yellow'

Instead, if we want to change the implementation of all instances of the class, we need to change the class. To demonstate this, let's first create an instance of Banana and call it original_banana:

> original_banana = new Banana();
Banana {}
> original_banana.getColor();
'green'

Now, let's change the implementation of the class method getColor. To do that, we have to use prototype:

> Banana.prototype.getColor = function() { return 'black'; }

Let's create a banana new_banana and see that it has the new color:

> new_banana = new Banana();
Banana {}
> new_banana.getColor();
'black'

Not only does the new banana have a new color, but the previously created banana uses the new implementation, too:

> original_banana.getColor();
'black'

However, recall that we changed the implementation of the instance of my_banana. That implementation stays intact:

> my_banana.getColor();
'yellow'

Python Function Redefinition

In Python, we can redefine functions in a similar way as what we did in javascript. Let's do the greeting example in Python. First, we define the original version of my_greeting:

def my_greeting():
    return 'hello'

Now, we can call it and print the result:

>>> print(my_greeting())
hello

Using the Python lambda syntax, we can redefine the function as follows:

>>> my_greeting = lambda: 'hola que tal'

Now, if we call it, it uses the new implementation:

>>> print(my_greeting())
hola que tal

Likewise, in Python, we can redefine functions of class instances. Let's define the class Banana:

class Banana:
    def get_color(self):
        return 'green'

Let's create an instance of Banana, call it my_banana and call get_color():

>>> my_banana = Banana()
>>> my_banana.get_color()
'green'

Next, let's redefine get_color. To do that we need to import types and then call types.MethodType:

>>> import types
>>> my_banana.get_color = types.MethodType(lambda self: 'yellow', my_banana)
>>> my_banana.get_color()
'yellow'

Changing the implementation for all instances of the class is similar. Instead of referencing the instance, we reference the class. Let's create an instance original_banana, then change the implementation of Banana.get_color, create the instance new_banana and call all get_color()'s:

>>> original_banana = Banana()
>>> Banana.get_color = types.MethodType(lambda self: 'black', Banana)
>>> new_banana = Banana()
>>> original_banana.get_color()
'black'
>>> new_banana.get_color()
'black'
>>> my_banana.get_color()
'yellow'

Even though original_banana was instantiated before the redefinition of get_color, it uses the new implementation. However, the custom implementation in my_banana.get_color stays intact.

Python Dynamic Classes

In Python, we have a concept of metaclassses. Using metaclasses, we can dynamically create classes.

Metaclasses have rather niche utility. As such, they are needed mostly in library development or similar. I will show an example of how metaclasses could be used. However, the example is rather long and, more importantly, not a recommended way of doing things. With the disclaimer out of the way, we are ready to proceed.

Let's say we want to create classes for various car models. The conventional (and preferred) way would be to create a class "Car" which would then include various information related to the car such as engine, price and whatever is needed. Furthermore, for our example, let's say we also have classses for the manufacturer:

class Model:
    def __init__(self, engine, price):
        self.engine = engine
        self.price = price

class Manufacturer:
    def __init__(self, models):
        self.models = models

Now, let's say we get some data according to which create instances, i.e. objects, of our classes:

cars_dict = {
    'Audi': {
        'A5': {'engine': 'ICE',  'price': 46000},
        'S5': {'engine': 'ICE',  'price': 55000},
        'e-tron': {'engine': 'electric', 'price': 102000},
    },
    'Porsche': {
        '911': {'engine': 'ICE', 'price': 214000},
        'Taycan': {'engine': 'electric', 'price': 194000},
    },
}

This data could then be read in a function as follows:

def create_cars_conventional(cars_dict):
    cars = {}
    for manufacturer in cars_dict:
        models = {}
        for model in cars_dict[manufacturer]:
            models[model] = Model(cars_dict[manufacturer][model]['engine'],
                                  cars_dict[manufacturer][model]['price'])

        cars[manufacturer] = Manufacturer(models)

    return cars

We could call this function and thereafter we could query the various instances for data:

>>> cars = create_cars_conventional(cars_dict)
>>> audi = cars['Audi']
>>> a5 = audi.models['A5']
>>> a5.engine
'ICE'
>>> a5.price
46000

For what it is worth, we could also directly query information of specific models:

>>> cars['Audi'].models['A5'].engine
'ICE'

However, what if we would like to create classes rather than instances of the cars? We can do that with metaprogramming. As classes are first-class citizens in Python, a class is an object. To create a class object, we call type() with the class name, the inherited base classes and the dictionary. For instance, our "Audi A5" class might look like:

>>> A5 = type('A5', (), dict(engine='ICE', price=46000))

and now we can use it like:

>>> A5.engine
'ICE'

However, we would probably like to have a function like create_cars_conventional which builds all classes for us. It could be as follows:

def create_cars_classes(cars_dict):
    classes_all = types.SimpleNamespace()
    for manufacturer in cars_dict:
        classes_models = {}
        for model in cars_dict[manufacturer]:
            class_name = 'Car{}{}'.format(manufacturer, model)
            car_engine = cars_dict[manufacturer][model]['engine']
            car_price = cars_dict[manufacturer][model]['price']
            car_class = type(class_name, (), dict(engine=car_engine, price=car_price))
            setattr(classes_all, class_name, car_class)

    return classes_all

Now it can be used like:

>>> cars = create_cars_classes(cars_dict)
>>> mycar = cars.CarAudiA5
>>> mycar.engine
'ICE'
>>> mycar.price
46000

As said, this is mainly a niche feature which most programmers will never need. But it has it's use in library development and so forth.

Conclusion

In this blog post I gave a definition for metaprogramming. Furthermore, I showed examples of what qualifies as metaprogramming. As we moved forward towards more complicated examples, the distinction between what is and isn't metaprogramming got less obvious. Ultimately, I wanted to show that metaprogramming can get somewhat esoteric. Moreover, I wanted to show that metaprogramming is rarely needed and solutions without metaprogramming should be considered first. Metaprogramming is mostly useful in library and similar scenarios, where we are effectively extending the programming language itself.

I wrote the same program in 5 different languages, this is what I learned

Michele Lindroos — Thu, 31 Mar 2022 06:36:15 +0000

For years I've wanted to have code I've written myself that can I look at when I need to write some projects from scratch. As I was working on jox, I noticed that the graph solving algorithm it needs would be an excellent program to write in different languages. In this blog post I document the different things I learned as I wrote the various implementations.

Background

I started programming at the age of 10 and this year I'm turning 35 and thus this is my 25th year of programming. As a teenager I wrote code for myself. Over the years I collected a vast codebase that I could reuse as I started something new.

This changed in 2008 as I started working on proprietary code for a company. Since 2012 I've worked as a full-time employee for various companies. Especially as I've switched from one company to another, I've often longed for the old code that I've written and that is now inaccessible to me.

Some years ago I got the idea of creating a set of code skeletons for various languages. While I had a clear need for it, the idea didn't sit too well with me. I had a clear idea that I want the skeletons to include at least build scripts and unit testing. However, the idea rubbed me in the wrong way as writing a silly program that does not solve any real world problem might be far too simple as reference.

As a side note, for many years now I've disliked how programming languages are often introduced by showing a simple hello world program. It shows some basic syntax of a language, but syntax isn't really the interesting part. Things like idioms and paradigms, metaprogramming support, error signalling and unit testing are what I care about.

As I was working on the design of the job dependency resolver algorithm in jox, I realized it was an excellent choice for creating sample code. I need unit tests for verification the test works. The algorithm is a graph algorithm. The graph can have loops, which typically complicates things somewhat. Furthermore, the algorithm would need to be able to detect faulty input, report the error and exit gracefully.

I wanted to write the algorithm in python, because python is often useful for many things and I've written a bunch of python already. I wanted to include an implementation in javascript, because it's a popular choice of language in many places. Furthermore, I used jest in a project and felt it was a rather nice unit testing library and I wanted to play around with it in my spare time.

I wanted to add an implementation in C++, because it has for many years been my favorite langauge. Also, as I've written many builds in CMake, I wanted to try out using Autotools. You can find my blog post detailing what I learned about Autoconf here: My Autoconf Primer.

Furthermore, Golang is currently a somewhat popular choice. Moreover, the list of successful projects written in Golang is impressive: Docker, Kubernetes and Terraform, just to name a few that I've used extensively myself, which are open-source.

Last but not least, I wanted to write an implementation in Scheme, because I've lately become interested in declarative programming and lambda calculus. Thus, I've been practicing Scheme.

To reiterate, the languages I wrote the algorithm in are:

python
javascript
C++
Golang
Scheme

As I wanted to test all the languages with the same tests, I created a unified test vector set using JSON. Now, if I want to modify test data, I need to only update JSON files and tests for all languages are updated synchronously.

Nowadays GitHub provides native test pipelines on their site called GitHub Action workflows. As I've written GitHub Actions previously, I decided to use them here as well. Therefore, all compilable code is compiled in GitHub workflows and all tests are run in GitHub workflows. Obviously, you can run the tests locally, too.

The repository for this project can be found here: https://github.com/keelefi/jox-algorithm

Note: At the time of writing this post, the Scheme implementation is still work-in-progress. Also, I might later add more languages. However, more importantly, I plan to update the code samples if I learn I'm using bad or outdated patterns etc.

In this section I presented the goals of the exercise. Furthermore, I described the choice of programming languages and skimmed through some related info. In the following sections I describe the various things I learned while doing this exercise, one per section, respectively.

JSON data should be formatted as objects

As described in the background section, I used JSON files to store test data. I had input test vectors under "input" and output test vectors under "output", respectively. However, under both of them, I put more keys, creating a hierarchy I expected would mimic the code I want to have. In other words, if I had input vectors "jobA" and "jobB", the JSON file would look something like:

{
"input": { 
     "jobA": { ... },     
     "jobB": { ... } 
}, 
... 
}

This is exactly how I ended up writing the code. However, there are JSON parsing libraries where the library automatically creates objects for you depending on the JSON data. These libraries expect lists of objects, instead of keys to objects as I used. Namely, I should've formatted the example JSON data as follows:

{
"input": [     
     { "name": "jobA", ... }, 
     { "name": "jobB",  ... } 
], 
...  
}

In this scenario I would've been able to fully use the automatically generated objects the various libraries provide.

Build setups are hard in every language

Already as a teenager I learned that setting up the build and dependencies in a new project can be cumbersome. At the time, I was only interested in creating builds on my own machine. As a I grew older and more professional, I got more interested in build reproducibility and having the build setup work on any machine. The increase in complexity as you want to have reproducible builds cannot be overstated. It is hard, and it is hard in every language.

I started my exercise writing the python build. I've used pip, virtualenv and pyenv and I was expecting this would be easy. I spent lots of time doing research online and ultimately I came to the conclusion it seems very hard to create a fully isolated build environment in python. Ultimately I gave up and just wrote a README.md containing instructions to install a few dependencies using pipenv. As this exercise is rather simple, this build is unlikely to fail, but then again, I failed to create solid reference material here.

With javascript I used npm. npm is very easy to setup. You use npm init to create a package.json where you populate dependencies and scripts for the build. In my case the only dependency was jest, which I use for unit testing. However, even though npm was very simple to use in this case, there are severe problems w.r.t. reproducibility and security when using npm. Packages can disappear and malicious packages can be uploaded to the package repository. Hence, like the solution I used for building python, the solution for javascript is not optimal, either.

With C++ I used Autoconf. As mention in the background section, I wrote a separate blog post on this experience. Autoconf was confusing to learn and I cannot recommend it to any proprietary inhouse projects where the build environment and target system are well-known. However, for open-source software where the integration is done by the user (or software distributor, such as a linux distribution like Debian or Fedora), Autoconf is very powerful.

Golang has it's own compiler which also ships the unit test executor. Golang was the easiest build setup in my scenario. I wrote a minimal go.mod containing one external dependency. The go.mod also contains the compiler version that is needed for compilation. Furthermore, running go will create a go.sum that, according to best practices, is uploaded in the git repository. This practice creates some extra commits in the repository as the dependencies are upgraded to newer versions. For this to work efficiently, you want good test coverage so that you can just bump versions as they're released. While I acknowledge this is opinionated, I think it's a good thing. Then again, I don't think this works nearly as well in FOSS scenarios, but I think the authors of Golang never had FOSS in mind. In fact, as far as I know, Golang compiles all code into a single binary and uses no dynamically linkable libraries.

Lastly I had Scheme. There's a multitude of implementations of Scheme interpreters. I use GNU Guile myself. I worry that my code would not work as well with other Scheme interpreters. Furthermore, Scheme is extended with SRFI's - Scheme Requests For Implementation. The SRFI's are numbered proposals for the various Scheme implementations to implement. In practice, your interpreter might ship with the SRFI you are looking for. If you're looking for a less common SRFI, you may have to find one from a separate source. But not all dependencies are SRFI's. In my case I wanted to use guile-json and this alone likely breaks the code on all other Scheme interpreters.

The Scheme SRFI system is actually very nice on a theoretical level. Anyone can create an SRFI, there's a clear way to improve the SRFI and after it's finalized, all the various interpreters can implement the SRFI as they see fit. This is extremely decentralized which is great. However, I see problems in the distribution of the SRFI implementations. If the interpreter doesn't ship the SRFI you are looking for, where do you get the SRFI? I can get it in many different ways, but there is no standardized way and that can be a headache for build reproducibility.

GitHub Action workflows are good and bad

I've worked with many CI systems over the years and I have to admit that GitHub Action workflows are by far the simplest and fastest to setup a simple build and test pipeline in. Of course, if you don't know the syntax like I do, it can take some time to setup a pipeline. But for me it took very minimal time to setup building and testing for all five languages.

The builds are not that straightforward, either. In the C++ build I use the distribution package manager extensively to install packages. In the Scheme build I clone the guile-json git repository. In all builds I use language specific tools for compiling (where applicable) and running the tests.

However, while it's easy to setup the steps to build and run tests, it's dramatically less simple to visualize the results. I would like to have a status matrix showing for each language the state of build and tests, respectively. In other words, for example, I would like to see at a glance if the C++ build works and if the C++ tests work, respectively. Even after spending considerable amount of time on this, I found no feasible way to achieve this. Instead, each workflow shows either "pass" or "failure", consolidating all steps into a single result.

For what it's worth, this is not unlike my previous experiences with GitHub Action workflows. When using Jenkins, it is very easy to get advanced build and test status visualization. For instance, you can show how many tests pass out of tests total. As far as I know, this is currently not possible to achieve in GitHub Actions. As such, I think GitHub Action workflows are a good fit for small FOSS projects like this exercise, but for serious software development you want something more advanced, even though the initial setup is more involved.

Python is great for algorithm prototyping and design

Already before I went to University, I used to sketch on paper (or in my head) the algorithms I needed to implement. At the University, this practice was reenforced and I liked to do UML's and whatnot. However, as I wrote increasingly complex algorithms, this practice didn't seem as feasible. I would end up with the best solution faster by just writing code and iterating the code.

Not all languages are alike in this regard. As I worked on this exercise, it became more apparent to me how different python and C++ are in this regard. I like C++ in many ways, but in C++ you need to write a considerable amount of boilerplate and making just trivial changes to data structures typically requires a magnitude more changes compared to similar changes in python.

There are many reasons for this discrepancy. One of the reasons is that the syntax of C++ is more expressive. In C++, even though we are working with a high-level language, we know exactly if we will get a hashmap (e.g. unordered_map), red-black tree (e.g. map or set) etc. In python you don't need to worry about this, which can be inefficient in production, but great for sketching.

Indeed, sketching out the algorithm design in python turned out very productive for me. As I hit a dead end, it didn't take much to make suitable changes and to get up to speed again. As such, python may be a good choice for prototyping in many scenarios.

Metaprogramming is awesome

Not only was it easy to sketch the algorithm proper in python, but also many things related to testing were easy in python and javascript as they have very extensive metaprogramming support. By comparison, the metaprogramming capabilities of C++ are less, but still rather powerful. In my experience, this is not the case in Golang, and it's painful.

For example, in all three of python, javascript and C++ I could have separate test cases in their own, dynamically generated, functions. In Golang I found no option for dynamic functions for every test data file and instead I had to create one function that reads the test vector files and then runs all of the tests. For what it's worth, this is also what I ended up doing in Scheme, but I'd say that is more because I don't know Scheme that well.

Metaprogramming is such a powerful tool that I plan on writing a separate blog post on it. I think that metaprogramming capabilities are a crucial feature of a programming language. With metaprogramming you can work around many otherwise nasty problems you are facing.

Exceptions are nice, but not necessary

All four other languages I used in this exercise support exceptions, but Golang does not. Instead, in Golang you return errors. This is similar to how you propagate errors in C. I know that many C++ programmers shy away from exceptions, but I've always liked them in all languages.

Indeed, I feel that also in this exercise the solutions in python, javascript and C++ were nicer than the the Golang solution due to the use of exceptions. When the algorithm faces an unrecoverable error scenario, it can just throw an exception. In contrast, with Golang I needed to add checks for function calls to see if an error occured.

This is obviously opinionated, and proponents of the Golang design will tell you that it's great that the caller of a function make it explicit that the function can return an error. While I tend to appreciate some explicitness, over the years I've learned to like it less.

That being said, the Golang solution for this exercise did not turn out as nasty as I was worried it would. Checking the errors in Golang doesn't clutter the code nearly as much I was expecting. Personally, I prefer exceptions, but I can live with the error propagating system present in Golang.

You are most productive in the language you know

This is an obvious point to make, but this was so emphasized during my exercise that I want to mention it. Even if you know the language syntax, if you are not familiar with idioms and patterns of a language, it will take a lot more time to write the code. I was, and still am, most familiar with python, javascript and C++. As I was writing code in these languages, I focused almost exclusively on the algorithm and the libraries I was using.

Compared to the three previously mentioned languages, with Golang I have far less mileage. For example, I wrote some structs, then later I had to rewrite them as I realized the idiomatic way to solve things in Golang are different. Golang is not a complicated language, but reaching the full solution required a lot of rewriting as I learned my earlier choices were bad. I also expect I will have to improve the Golang code in the future more than the three other implementations.

Scheme is the one I have the least mileage with. In fact, even though I spent more time on Scheme than any other language, I didn't get even close to the full solution. However, I don't think Scheme is harder in itself. I think Scheme is magnitudes simpler than C++. The thing is that I'm used to imperative programming and Scheme is based on lambda calculus, which is fundamentally different. The way I see it, I have over 20 years worth of experience writing imperative code and less than 1 year worth of experience writing lambda calculus. Therefore, I'm currently very slow in writing Scheme.

Popular languages have an advantage in stack overflow questions and answers

Writing python and javascript was fast not only because I knew the languages, but also because I could ask google any question that popped in my head and a related stack overflow question and answer would be available, respectively. The answers are not poor quality, either, but rather, they often explain the background and guide you to idiomatic solutions and solid patterns, which I find very nice.

As I moved on to write the Scheme solution, this became very clear. Many questions I wanted to ask had not been asked anywhere. I had to do a lot more work to find the relevant information I was looking for. This slowed me down considerably. However, more importantly, I'm also less confident my solutions and the patterns I'm using in Scheme are good. Frankly, I feel they aren't.

For what it is worth, as I was stuck with the Scheme implementation, I even ended up creating a stack overflow account so that I could ask a question myself. It was a nice experience: I asked my question on a Sunday morning and a few hours later it was already answered. The answer was off the topic, but I asked clarifying questions and the same guy ultimately answered my original question. I hope my question will be useful to someone else, too!

I hope to learn more Scheme and lambda calculus

Even though I didn't finish the Scheme implementation, it was fun and exciting to write it. Pretty much everything is different in Scheme compared to the mostly imperative languages I'm used to. While it was rather easy to write the algorithm in python (and then copy the solution to javascript, C++ and Golang), I'm not too happy with the result. As I have extensive testing, I know the python solution works correctly. But it's not beautiful, and, in fact, it might not be optimal, either.

Over this blog post, I've described the other languages as imperative. However, the division between imperative and declarative is not clearcut. For example, C was clearly designed as an imperative language. It was meant to be an abstraction layer for assembly code. The original use case was to compile C to different assembly languages.

While the original use case still stands (even though most code now exclusively runs on x86), processors are now far more complex and compilers are way more powerful at optimizing. Instead of executing the C program the programmer wrote, the compiler and processor will run the equivalent, but optimized, program. This is especially important when considering multi-threaded programs running on multicore systems. For more information on the topic, I suggest the interested reader watch the talk Atomic weapons by Herb Sutter.

I think that Scheme and lambda calculus has still a lot to give to me and the programming industry in general. In fact, I feel like over the decades we are slowly moving away from the computation model Alan Turing envisioned and toward lambda calculus, as described by Alonzo Church. For what it's worth, Turing machines and lambda calculus are equivalent.

As I've understood, many hope that functional programming would make simultaneous multiprocessing more feasible. While I personally don't see the connection that strong, I think that writing declarative code is more productive and meaningful compared to the imperative counterpart. After all, at the end of the day, we have the computer make mathematical calculations, and we don't care what middle steps it does, as long as it ultimately returns the solution to our question. This is fundamentally declarative, not imperative.

Future work

Obviously, as the Scheme implementation is still work-in-progress, I want to learn more Scheme and I have fun writing it, I hope to finish the Scheme implementation. Currently, I'm stuck working on a depth-first-search algorith in Scheme.

As I mentioned earlier in the blog post, I'm planning on writing a blog post about metaprogramming. I think it would be fun and useful. Similarly, I might write something about the differences between imperative and declarative programing, as I'm currently quite interested in the topic.

Also, I hope to keep updating the jox-algorithm repository relevant to this blog post. I hope to update the build setups as I learn more about reproducible builds, as I think that would be very useful. I might also change from GitHub Action workflows to something else. Also, as I learn better programming patterns, I hope to fix any bad or outdated patterns I'm currently using.

I don't expect anyone to make pull requests, but I'm open to pull requests in case someone finds this exercise useful as reference material when starting new projects in various languages.

Conclusion

In this blog post I describe my hobby project I've been sporadically working on for a few months or so. I wrote the same code in five different languages: python, javascript, C++, Golang and Scheme. In this blog post I describe various things I learned while doing the exercise. If you found this blog post useful or have opinions or questions about my points, feel free to comment below. I also accept pull request to the repository if you find it useful as reference material.

My Autoconf Primer

Michele Lindroos — Wed, 09 Feb 2022 20:43:23 +0000

Since a young age I've learned that build systems and dependency management range from difficult to mind-bogglingly frustrating. My best experiences have been with Autotools, which might surprise many. However, I had never made anything serious from scratch using Autotools myself, but rather only modified things setup by others. Lately I had some positive experiences building C programs linking libguile with Autoconf and this prompted me to try something bigger. I setup the build toolchain for a C++ program using Autotools. In this blog post I attempt to document what I learned along the way.

Autotools, Automake and Autoconf

The first question I wanted answered is if I should be using Autotools, Autoconf or even Automake. The answer is that Autotools is not a binary or similar, but rather it's an umbrella term for Autoconf, Automake and everything related. On the other hand, automake is a binary that converts a Makefile.am into Makefile.in.

In my brand new program, I needed to learn very little about Automake. I created a top-level Makefile.am containing a pointer to the related documentation and an instruction to recurse into the subdirectory src:

$ cat Makefile.am
SUBDIRS = src
dist_doc_DATA = README.md

The file in src/Makefile.am contains information of the sources to compile into objects and the resulting binaries:

$ cat src/Makefile.am 
bin_PROGRAMS = test_algorithm
test_algorithm_SOURCES = \
    algorithm.cpp \
    exception.cpp \
    job.cpp \
    warning.cpp \
    test_algorithm.cpp

You can run automake as a standalone program. However, I found it far more convenient to call it using autoreconf. autoreconf is a program that runs automake and autoconf (and more) conveniently for you. Typically, I run autoreconf with the following switches: -i to generate missing auxiliary files, -v for verbose output and -f to force regeneration of all configuration files.

$ autoreconf -vif

But now I'm getting ahead of myself. Before we can run autoreconf, we need to write the input for autoconf, namely, configure.ac.

Introduction to Autoconf

The role of Autoconf is to generate the configure to ship with a software distribution. The input file configure.ac is formatted in the macro language M4.

Now, this might be a bit confusing, but configure (and hence autoconf) is not meant to work with software dependency management. Instead, the main design principle of Autoconf is to work with features and capabilities of the installed system where the distributed software is compiled.

config.h

Although I didn't use it myself, I need to mention config.h. (for what it is worth, I should probably try it out and update this part of the blog post later)

As a result of running configure, a header file config.h is typically generated. This header file contains detected capabilities of the system we are running the compilation on. For example, if we look for pthread, config.h will contain suitable #define's to indicate if pthread is found and linkable or not.

As stated previously, I did not utilize config.h and therefore no such file is generated in my case.

Structure of configure.ac

The first statement of configure.ac must be AC_INIT and the last must be AC_OUTPUT. The rest of the statements can be placed anywhere, except for when they depend on each other. This dynamic seems to have created a de facto standard structure for configure.ac files. Even the Autoconf manual has a section Standard configure.ac Layout. However, I find it quite confusing and instead I follow a mental picture, which is as follows:

Initialization
Compiler settings
Configuration Files
Dependencies
Output

As previously stated, AC_INIT is the first statement. It accepts parameters such as program name, program version, maintainer e-mail address etc. In my case it is:

AC_INIT([algorithm], [1.0])

As part of the initialization phase, I also put a statement to initialize automake with AM_INIT_AUTOMAKE. I found this in the automake manual. Note that statements starting with AC_ are for Autoconf and statements starting with AM_ are macros for Automake. However, AM_INIT_AUTOMAKE is the only statement for Automake in my case.

Now, this is really important: We give some parameters that look just like compiler flags, but they are for Automake when it generates Makefile.in etc. I used -Wall, -Werror and foreign. I needed foreign, because otherwise Automake requires all the files in a standard GNU package, i.e. NEWS, README, AUTHORS and ChangeLog. My AM_INIT_AUTOMAKE is as follows:

AM_INIT_AUTOMAKE([-Wall -Werror foreign])

Compiler settings

Next we need to select a compiler. When compiling a standard C program, we use AC_PROG_CC. In my case, I'm compiling C++ so I use AC_PROG_CXX instead. Note that the macro AC_PROG_CPP is related to the C preprocessor and has nothing to do with C++ (for the C++ preprocessor command, use the macro AC_PROG_CXXCPP).

The only parameter that AC_PROG_CC and AC_PROG_CXX accept are a compiler search list, but no compiler flags. Instead, if you want to specify compiler flags, you need to set CFLAGS or CXXFLAGS before calling the macro. As per the Autoconf manual, by default AC_PROG_{CC,CXX} sets {C,CXX}FLAGS} to -g -O2 (or -g if the detected compiler is not a GNU compiler). But if {C,CXX}FLAGS was already set, it's kept unchanged.

In my case, I call the macro AC_PROG_CXX with the following construct:

: ${CXXFLAGS="-g -O2 -Wall -Werror"}
AC_PROG_CXX

Furthermore, as my source code uses C++17 features, I use an extra macro for that. But it's a little special and I will come back to it later in the section Autoconf Archive.

Configuration files

As explained earlier, Automake compiles an Makefile.in from Makefile.am. However, this Makefile.in is not yet a Makefile. To specify which makefiles need to be compiled, we use the macro AC_CONFIG_FILES. In my case:

AC_CONFIG_FILES([
    Makefile
    src/Makefile
])

Note that we will still distribute the Makefile.in and the Makefile will be generated only on site. The instructions to build the file are contained in config.status while the configure will use.

Furthermore, the utility of AC_CONFIG_FILES is not retricted to makefiles, but other files can be specified, too. However, I had no such use.

Dependencies

As explained earlier, Autoconf doesn't work with software dependency managers in the conventional sense. I'll call this section Dependencies anyhow, as that's how I think about it. There are various things you can do here, and in my case I was happy I needed 3 different ways to search for libraries and headers, as that really made me learn.

Dependencies: AC_CHECK_LIB

The most typical thing you would do is AC_CHECK_LIB. To AC_CHECK_LIB you give the library name, a symbol in the library, and, optionally, a code segment to execute on success and a code segment to execute on failure. For example, in my scenario I ended up doing

AC_CHECK_LIB([pthread], [pthread_create], [], [AC_MSG_ERROR([pthread is not installed.])])

My first surprise was that a symbol from the library is needed. In fact, the macro will expand into a C program that will be compiled. The source of the C program will contain the symbol we indicated, i.e. pthread_create and the program will be linked against the library, i.e. with the flag -lpthread. If compilation succeeds, the third parameter will be executed, but since its [] the default action will be taken. Note that to disable the default action you can do [ ]. If compilation fails, we run the fourth parameter which is a macro to signal an error and halt operation.

The default action is to add the specified library to LIBS, i.e. in my case LIBS="-lpthread $LIBS" (yes, I double-checked from the generatedconfigure). Furthermore, the defineHAVE_LIBlibrarywill be set. In my case, it's#define HAVE_LIBPTHREAD 1`.

I think there's at least two takeaways here. First of all, we don't match libraries with any kind of versioning. Instead, we look for a symbol. I would assume this can cause headache with missing or deprecated features. Furthermore, the macro AC_CHECK_LIB uses always C linking. This means that C++ libraries cannot be added using this construct, unless the library also has some symbols using C linking (i.e. extern "C").

Dependencies: Linking C++ libraries

Since we can't use AC_CHECK_LIB for linking C++ code, what other options do we have? There's a macro AX_CXX_CHECK_LIB, but that is not distributed as part of Autoconf and not even the Autoconf Archive, so I have decided against using it.

Instead, I found a blog post that suggests writing your own check. The basic idea is to use the macro AC_LINK_IFELSE (this is the same macro as AC_CHECK_LIB uses). To AC_LINK_IFELSE you give a source to compile and a segment to run on success and a segment to run on failure. In my case:

AC_LINK_IFELSE(
    <source here>,
    [HAVE_<library>=1],
    [AC_MSG_ERROR([<library> is not installed.])])

To generate the source code that is used to verify linking, the blog post suggests using the macro AC_LANG_PROGRAM. The macro takes to parameters, a prologue and a body. In my case:

AC_LANG_PROGRAM([#include <gtest/gtest.h>], [EXPECT_EQ(1,1)])

We are still missing two pieces here. First, even though we set AC_PROG_CXX, we have never set the language to use when running compilation tests. This is done using the macro AC_LANG. By setting AC_LANG(C++), AC_LINK_IFELSE will use a C++ compiler (and linker) rather than the default choice of a C compiler.

Furthermore, on success, AC_CHECK_LIB will add the specified library to the variable LIBS. Therefore, we have to do it manually. If we would want to be really fancy, we could unset the library from LIBS, if the test fails. Since we exit on failure, we don't unset anything.

Here's the whole block of code:

AC_LANG(C++)
LIBS="-lgtest $LIBS"
AC_LINK_IFELSE(
    [AC_LANG_PROGRAM([#include <gtest/gtest.h>], [EXPECT_EQ(1,1)])],
    [HAVE_GTEST=1],
    [AC_MSG_ERROR([gtest is not installed.])])

Dependencies: Headers

Some dependencies are merely headers. To check the availability of a header, there's the macro AC_CHECK_HEADER. This macro takes the header as it would be used in a #include preprocessor directive. Furthermore, you can specify an action to take on success and on failure, respectively. In my case, I'm using the header-only library nlohmann-json and only headers from gmock, and thus I'm using the following two statements:

AC_CHECK_HEADER([nlohmann/json.hpp], [], [AC_MSG_ERROR([nlohmann-json is not installed.])])
AC_CHECK_HEADER([gmock/gmock.h], [], [AC_MSG_ERROR([gmock is not installed.])])

Dependencies: pkg-config

The idea behind pkg-config seems simple enough: it's a program that can be used to query for installed software and their versions, respectively. pkg-config requires software to be distributed with package metadata contained in a .pc file. The metadata file will contain various information of the package, such as CFLAGS and LIBS. Sounds like a replacement for AC_CHECK_LIB, right?

The Autoconf Archives provides the macro AX_PKG_CHECK_MODULES. However, on various online forums and blogs, I found warnings about how Autoconf and pkg-config have a fundamentally different approach. Therefore, I decided against using pkg-config in my setup.

As I understand it, one problem is that merely the success or failure of running pkg-config does not adequately indicate if linking the package works. For example, if pkg-config is not installed, the test may fail, even though the dependency we are looking for exists and is linkable. Likewise, there can be a discrepancy between how pkg-config and our compiler/linker of choice works. Lastly, the information in the .pc file can be wrong. The last point is probably relevant when chrooting or similar.

All of configure.ac

In the previous sections, I've explained all of my configure.ac, with the exception of AC_OUTPUT. There's not much to it: we just have to call it in the end of configure.ac, as it will generate the files needed for Automake.

My whole configure.ac is as follows (comments included):

$ cat configure.ac
AC_INIT([algorithm], [1.0])
AM_INIT_AUTOMAKE([-Wall -Werror foreign])

: ${CXXFLAGS="-g -O2 -Wall -Werror"}
AC_PROG_CXX

# check that compiler supports c++17 and set -std=c++17
AX_CXX_COMPILE_STDCXX_17([noext], [mandatory])

AC_CONFIG_FILES([
    Makefile
    src/Makefile
])

AC_CHECK_LIB([pthread], [pthread_create], [], [AC_MSG_ERROR([pthread is not installed.])])

# AC_CHECK_LIB doesnt work well with C++ linking. Instead, we use a test program to see if linking of gtest works.
AC_LANG(C++)
LIBS="-lgtest $LIBS"
AC_LINK_IFELSE(
    [AC_LANG_PROGRAM([#include <gtest/gtest.h>], [EXPECT_EQ(1,1)])],
    [HAVE_GTEST=1],
    [AC_MSG_ERROR([gtest is not installed.])])

# nlohmann-json is a header only library.
AC_CHECK_HEADER([nlohmann/json.hpp], [], [AC_MSG_ERROR([nlohmann-json is not installed.])])

# we need gmock headers even though we don't link it
AC_CHECK_HEADER([gmock/gmock.h], [], [AC_MSG_ERROR([gmock is not installed.])])

AC_OUTPUT

Recap on Usage

Alright, so you've created all the needed source files and now you wonder what commands to use? First, we do
autoreconf to generate configure, Makefile.in and many more files:

$ autoreconf -vif

Note: This step is only done by package maintainers.

To the end-user, we ship all of configure, Makefile.in's etc. The first command the end-user does is to run the
configure script:

$ ./configure

If we, as the package maintainers, did everything correctly, running configure at the end-user will either fail, if
the program (or library) would never be able to compile or run properly. Likewise, assuming we did everything correctly,
if configure succeeds, then also compiling and running the program (or library) will work.

To build the source:

$ make

Note that if we did everything correctly, overriding compiler flags with CXXFLAGS (or CFLAGS if C program), linkable
libraries with LIBS etc will work properly.

The Autoconf Archives

The Autoconf Archives is a separate software distribution from Autoconf itself. It contains a multitude of macros that can be used when generating the configure. Note that it's not an issue to depend on the Autoconf Archives, as we don't distribute the configure.ac, but instead we distribute configure. Hence, the end-user needs neither Autoconf nor the Autoconf Archives.

Conclusion

In this post I went through what I learned as I setup a C++ project which is built with Autoconf (and Automake). Autoconf is quite different from CMake and other build systems. For this reason it's probably off-putting for newcomers as many things seem unnecessarily complicated. However, in my experience, well-written configure files tend to work far better on various systems compared to many other solutions. I doubt I've reached that level of understanding, but everyone needs to start somewhere :-)

While it was definitely frustrating to figure out many things about Autoconf, I'm happy I did it. I feel I understand the world of package management and software distribution a tad better.