FizzBuzz with higher-order cpp macros and ELF linker sets

[fanf]

Here are a couple of fun ways to reduce repetitive code in C. To illustrate them, I'll implement FizzBuzz with the constraint that I must mention Fizz and Buzz only once in each implementation.

The generic context is that I want to declare some functions, and each function has an object containing some metadata. In this case the function is a predicate like "divisible by three" and the metadata is "Fizz". In a more realistic situation the function might be a driver entry point and the metadata might be a description of the hardware it supports.

Both implementations of FizzBuzz fit into the following generic FizzBuzz framework, which knows the general form of the game but not the specific rules about when to utter silly words instead of numbers.

    #include <stdbool.h>
    #include <stdio.h>
    #include <err.h>
    
    // predicate metadata
    typedef struct pred {
        bool (*pred)(int);
        const char *name;
    } pred;
    
    // some other file declares a table of predicates
    #include PTBL
    
    static bool putsafe(const char *s) {
        return s != NULL && fputs(s, stdout) != EOF;
    }
    
    int main(void) {
        for (int i = 0; true; i++) {
            bool done = false;
            // if a predicate is true, print its name
            for (pred *p = ptbl; p < ptbl_end; p++)
                done |= putsafe(p->pred(i) ? p->name : NULL);
            // if no predicate was true, print the number
            if (printf(done ? "\n" : "%d\n", i) < 0)
                err(1, "printf");
        }
    }

To compile this code you need to define the PTBL macro to the name of a file that implements a FizzBuzz predicate table.

Higher-order cpp macros

A higher-order macro is a macro which takes a macro as an argument. This can be useful if you want the macro to do different things each time it is invoked.

For FizzBuzz we use a higher-order macro to tersely define all the predicates in one place. What this macro actually does depends on the macro name p that we pass to it.

    #define predicates(p) \
        p(Fizz, i % 3 == 0) \
        p(Buzz, i % 5 == 0)

We can then define a function-defining macro, and pass it to our higher-order macro to define all the predicate functions.

    #define pred_fun(name, test) \
        static bool name(int i) { return test; }
    
    predicates(pred_fun)

And we can define a macro to declare a metadata table entry (using the C preprocessor stringification operator), and pass it to our higher-order macro to fill in the whole metadata table.

    #define pred_ent(name, test) { name, #name },
    
    pred ptbl[] = {
        predicates(pred_ent)
    };

For the purposes of the main program we also need to declare the end of the table.

    #define ptbl_end (ptbl + sizeof(ptbl)/sizeof(*ptbl))

Higher-order macros can get unweildy, especially if each item in the list is large. An alternative is to use a higher-order include file, where instead of passing a macro to another macro, you #define a macro with a particular name, #include a file of macro invocations, then #undef the special macro. This saves you from having to end dozens of lines with backslash continuations.

ELF linker sets

The linker takes collections of definitions, separates them into different sections (e.g. code and data), and concatenates each section into a contiguous block of memory. The effect is that although you can interleave code and data in your C source file, the linker disentangles the little pieces into one code section and one data section.

You can also define your own sections, if you like, by using gcc declaration attributes, so the linker will gather the declarations together in your binary regardless of how spread out they were in the source. The FreeBSD kernel calls these "linker sets" and uses them extensively to construct lists of drivers, initialization actions, etc.

This allows us to declare the metadata for a FizzBuzz predicate alongside its function definition, and use the linker to gather all the metadata into the array expected by the main program. The key part of the macro below is the __attribute__((section("pred"))).

    #define predicate(name, test) \
        static bool name(int i) { return test; } \
        pred pred_##name __attribute__((section("pred"))) \
            = { name, #name }

With that convenience macro we can define our predicates in whatever order or in whatever files we want.

    predicate(Fizz, i % 3 == 0);
    predicate(Buzz, i % 5 == 0);

To access the metadata, the linker helpfully defines some symbols identifying the start and end of the section, which we can pass to our main program.

    extern pred __start_pred[], __stop_pred[];
    
    #define ptbl    __start_pred
    #define ptbl_end __stop_pred

Source code

git clone https://github.com/fanf2/dry-fizz-buzz

Comments

[simont]

Of course, if you're not committed to using the same main() for both versions of this, there's no reason the higher-order macro approach needs a table at all:

#define pred_justdoit(name, test) \
    if (test) { putsafe(#name); done = true; }

Then you can replace the for-loop that iterates over the predicate table with a simple predicates(pred_justdoit).

[fanf]

Good point - My example doesn't do full justice to the power of macros :-)

[simont]

For a laugh, a few years ago, I wrote agedu's entire command-line option parser using a single master list of option names and characteristics in a higher-order macro, using different invocations of the same macro to generate both data tables and code :-)

[simont]

Also, I'm intrigued by the feature that an error writing to standard output will cause your program to lose the game :-)

[fanf]

Yes, maybe I should have some more thorough error checking earlier :-P

Even before ELF

[(Anonymous)]

When we implemented this feature originally, it was a GNU ld extension invoked by special .stabs directives; it predates ELF (or at least our adoption of ELF). If you didn't have GNU ld, or couldn't use it for some reason, there was a utility called "collect" which would extract these things from the object files and generate a new object file to be included in the loader command line. Of course this was implemented originally to provide for static constructors in C++.

Re: Even before ELF

[fanf]

Cool, thanks for that nugget of history! I only learned about linker sets post-ELF, about 15 years ago. At last I know what collect was about :-)