Metalang99

The dark side of the force is a pathway to many abilities, some considered to be unnatural.
-- Darth Sidious

Based on examples/demo.c:

Compile-time list manipulation

// 3, 3, 3, 3, 3
static int five_threes[] = {
    ML99_LIST_EVAL_COMMA_SEP(ML99_listReplicate(v(5), v(3))),
};

// 5, 4, 3, 2, 1
static int from_5_to_1[] = {
    ML99_LIST_EVAL_COMMA_SEP(ML99_listReverse(ML99_list(v(1, 2, 3, 4, 5)))),
};

// 9, 2, 5
static int lesser_than_10[] = {
    ML99_LIST_EVAL_COMMA_SEP(
        ML99_listFilter(ML99_appl(v(ML99_greater), v(10)), ML99_list(v(9, 2, 11, 13, 5)))),
};

Macro recursion

#define factorial(n)          ML99_natMatch(n, v(factorial_))
#define factorial_Z_IMPL(...) v(1)
#define factorial_S_IMPL(n)   ML99_mul(ML99_inc(v(n)), factorial(v(n)))

ML99_ASSERT_EQ(factorial(v(4)), v(24));

Overloading on a number of arguments

typedef struct {
    double width, height;
} Rect;

#define Rect_new(...) ML99_OVERLOAD(Rect_new_, __VA_ARGS__)
#define Rect_new_1(x)                                                                              \
    { x, x }
#define Rect_new_2(x, y)                                                                           \
    { x, y }

static Rect _7x8 = Rect_new(7, 8), _10x10 = Rect_new(10);

// ... and more!

int main(void) {
    // Yeah. All is done at compile time.
}

(Hint: v(something) evaluates to something.)

Metalang99 is a firm foundation for writing reliable and maintainable metaprograms in pure C99. It is implemented as an interpreted FP language upon preprocessor macros: just #include <metalang99.h> and you are ready to go. Metalang99 features algebraic data types, pattern matching, recursion, currying, and collections; in addition, it provides a means for compile-time error reporting and debugging.

Note: most of the time, you would not use Metalang99 directly but through userland libraries such as Datatype99 and Interface99 (see below).

Motivation

Macros facilitate code re-use, macros are the building material that lets you shape the language to suit the problem being solved, leading to more clean and concise code. However, metaprogramming in C is utterly castrated: we cannot even operate with control flow, integers, unbounded sequences, and compound data structures, thereby throwing a lot of hypothetically useful metaprograms out of scope.

To solve the problem, I have implemented Metalang99. Having its functionality at our disposal, it becomes possible to develop even fairly non-trivial metaprograms, such as Datatype99:

#include <datatype99.h>

datatype(
    BinaryTree,
    (Leaf, int),
    (Node, BinaryTree *, int, BinaryTree *)
);

int sum(const BinaryTree *tree) {
    match(*tree) {
        of(Leaf, x) return *x;
        of(Node, lhs, x, rhs) return sum(*lhs) + *x + sum(*rhs);
    }
}

Or Interface99:

#include <interface99.h>

#include <stdio.h>

#define Shape_IFACE                      \
    vfunc( int, perim, const VSelf)      \
    vfunc(void, scale, VSelf, int factor)

interface(Shape);

typedef struct {
    int a, b;
} Rectangle;

int  Rectangle_perim(const VSelf) { /* ... */ }
void Rectangle_scale(VSelf, int factor) { /* ... */ }

impl(Shape, Rectangle);

typedef struct {
    int a, b, c;
} Triangle;

int  Triangle_perim(const VSelf) { /* ... */ }
void Triangle_scale(VSelf, int factor) { /* ... */ }

impl(Shape, Triangle);

void test(Shape shape) {
    printf("perim = %d\n", VCALL(shape, perim));
    VCALL(shape, scale, 5);
    printf("perim = %d\n", VCALL(shape, perim));
}

Unlike the vague techniques, such as tagged unions or virtual method tables, the above metaprograms leverage type safety, syntax conciseness, and maintain the exact memory layout of generated code.

Looks interesting? Check out the motivational post for more information.

Getting started

Download this repository.
Add metalang99/include to your include paths.
#include <metalang99.h> beforehand (or use separate headers described in the docs).

Some handy advices:

PLEASE, use Metalang99 only with -ftrack-macro-expansion=0 (GCC), -fmacro-backtrace-limit=1 (Clang), or something similar, otherwise it will throw your compiler to the moon.
Precompile headers that use Metalang99 so that they will not be compiled each time they are included. It is helpful to reduce compilation times, but they are not mandatory.

Tutorial | Examples | User documentation

Happy hacking!

Highlights

Macro recursion. Recursive calls behave as expected. In particular, to implement recursion, Boost/Preprocessor just copy-pastes all recursive functions up to a certain limit and forces to either keep track of recursion depth or rely on a built-in deduction; Metalang99 is free from such drawbacks.
Almost the same syntax. Metalang99 does not look too alien in comparison with Order PP because the syntax differs insignificantly from usual preprocessor code.
Partial application. Instead of tracking auxiliary arguments here and there (as it is done in Boost/Preprocessor), partial application allows to capture an environment by applying constant values first. Besides that, partial application facilitates better reuse of metafunctions.
Debugging and error reporting. You can conveniently debug your macros with ML99_abort and report fatal errors with ML99_fatal. The interpreter will immediately finish its work and do the trick.

Philosophy and origins

My work on Poica, a research programming language implemented upon Boost/Preprocessor, has left me unsatisfied with the result. The fundamental limitations of Boost/Preprocessor have made the codebase simply unmaintainable; these include recursive macro calls (blocked by the preprocessor), which have made debugging a complete nightmare, the absence of partial application that has made context passing utterly awkward, and every single mistake that resulted in megabytes of compiler error messages.

Only then I have understood that instead of enriching the preprocessor with various ad-hoc mechanisms, we should really establish a clear paradigm in which to structure metaprograms. With these thoughts in mind, I started to implement Metalang99...

Long story short, it took half of a year of hard work to release v0.1.0 and almost a year to make it stable. As a real-world application of Metalang99, I created Datatype99 exactly of the same form I wanted it to be: the implementation is highly declarative, the syntax is nifty, and the semantics is well-defined.

Finally, I want to say that Metalang99 is only about syntax transformations and not about CPU-bound tasks; the preprocessor is just too slow and limited for such kind of abuse.

Guidelines

If possible, assert macro parameters for well-formedness using ML99_assertIsTuple, ML99_assertIsNat, etc. for better diagnostic messages.
Prefer the ## token-pasting operator inside Metalang99-compliant macros instead of ML99_cat or its friends, because arguments will nevertheless be fully expanded.
Use ML99_todo and its friends to indicate unimplemented functionality.

Publications

What’s the Point of the C Preprocessor, Actually? by Hirrolot.
Macros on Steroids, Or: How Can Pure C Benefit From Metaprogramming by Hirrolot.
Extend Your Language, Don’t Alter It by Hirrolot.

Contributing

See CONTRIBUTING.md.

Architecture

See ARCHITECTURE.md.

Idioms

See idioms.md.

Optimisation tips

See optimization_tips.md.

FAQ

Q: What about compile-time errors?

A: Metalang99 is a big step towards understandable compiler diagnostics. It has a built-in syntax checker that tests all incoming terms for validity:

[playground.c]

ML99_EVAL(123)
ML99_EVAL(x, y, z)
ML99_EVAL(v(Billie) v(Jean))

[/bin/sh]

$ gcc playground.c -Imetalang99/include -ftrack-macro-expansion=0
playground.c:3:1: error: static assertion failed: "invalid term `123`"
    3 | ML99_EVAL(123)
      | ^~~~~~~~~
playground.c:4:1: error: static assertion failed: "invalid term `x`"
    4 | ML99_EVAL(x, y, z)
      | ^~~~~~~~~
playground.c:5:1: error: static assertion failed: "invalid term `(0v, Billie) (0v, Jean)`, did you miss a comma?"
    5 | ML99_EVAL(v(Billie) v(Jean))
      | ^~~~~~~~~

Metalang99 can even check for macro preconditions and report an error:

[playground.c]

ML99_EVAL(ML99_listHead(ML99_nil()))
ML99_EVAL(ML99_unwrapLeft(ML99_right(v(123))))
ML99_EVAL(ML99_div(v(18), v(4)))

[/bin/sh]

$ gcc playground.c -Imetalang99/include -ftrack-macro-expansion=0
playground.c:3:1: error: static assertion failed: "ML99_listHead: expected a non-empty list"
    3 | ML99_EVAL(ML99_listHead(ML99_nil()))
      | ^~~~~~~~~
playground.c:4:1: error: static assertion failed: "ML99_unwrapLeft: expected ML99_left but found ML99_right"
    4 | ML99_EVAL(ML99_unwrapLeft(ML99_right(v(123))))
      | ^~~~~~~~~
playground.c:5:1: error: static assertion failed: "ML99_div: 18 is not divisible by 4"
    5 | ML99_EVAL(ML99_div(v(18), v(4)))
      | ^~~~~~~~~

However, if you do something awkward, compile-time errors can become quite obscured:

// ML99_PRIV_REC_NEXT_ML99_PRIV_IF_0 blah(ML99_PRIV_SYNTAX_CHECKER_EMIT_ERROR, ML99_PRIV_TERM_MATCH) ((~, ~, ~) blah, ML99_PRIV_EVAL_)(ML99_PRIV_REC_STOP, (~), 0fspace, (, ), ((0end, ~), ~), ~, ~ blah)(0)()
ML99_EVAL((~, ~, ~) blah)

In either case, you can try to iteratively debug your metaprogram.

Q: What about debugging?

A: See the chapter Testing, debugging, and error reporting.

Q: What about IDE support?

A: I use VS Code for development. It enables pop-up suggestments of macro-generated constructions but, of course, it does not support macro syntax highlighting.

Q: Compilation times?

A: To run the benchmarks, execute ./scripts/bench.sh from the root directory.

Q: How does it work?

Because macro recursion is prohibited, there is an ad-hoc recursion engine which works by deferring macro expansions and passing continuations here and there.
Upon it, the continuation-passing style interpreter reduces language expressions into final results.
The standard library is nothing but a set of metafunctions implemented using the core metalanguage, i.e. they are to be evaluated by the interpreter.

Q: Why not third-party code generators?

A: See the blog post What’s the Point of the C Preprocessor, Actually?

Q: Is it Turing-complete?

A: The C/C++ preprocessor is capable to iterate only up to a certain limit. For Metalang99, this limit is defined in terms of reductions steps: once a fixed amount of reduction steps has exhausted, your metaprogram will not be able to execute anymore.

Q: Why macros if we have templates?

A: Metalang99 is primarily targeted at pure C, and C lacks templates. But anyway, you can find the argumentation for C++ at the website of Boost/Preprocessor.

Q: Where is an amalgamated header?

A: I am against amalgamated headers because of burden with updating. Instead, you can just add Metalang99 as a Git submodule and update it with git submodule update --remote.

Q: Which standards are supported?

A: C99/C++11 and onwards.

Q: Which compilers are tested?

A: Metalang99 is known to work on these compilers:

GCC
Clang
MSVC
TCC

undarkaido / metalang99 Goto Github PK

metalang99's Introduction