diff options
Diffstat (limited to 'test/external/metalang99/README.md')
| -rw-r--r-- | test/external/metalang99/README.md | 391 |
1 files changed, 391 insertions, 0 deletions
diff --git a/test/external/metalang99/README.md b/test/external/metalang99/README.md new file mode 100644 index 0000000..6985549 --- /dev/null +++ b/test/external/metalang99/README.md @@ -0,0 +1,391 @@ +# Metalang99 + +[](https://github.com/hirrolot/metalang99/actions) +[](https://metalang99.readthedocs.io/en/latest/) +[](https://hirrolot.gitbook.io/metalang99/) +[](https://github.com/hirrolot/metalang99/blob/master/spec/spec.pdf) + +> The dark side of the force is a pathway to many abilities, some considered to be unnatural.<br>    <b>-- Darth Sidious</b> + +Based on [`examples/demo.c`](examples/demo.c): + +<table> +<tr><td><b>Compile-time list manipulation</b></td></tr> + +<tr> +<td> + +```c +// 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)))), +}; +``` + +</td> +</tr> +</table> + +<table> +<tr><td><b>Macro recursion</b></td></tr> + +<tr> +<td> + +```c +#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)); +``` + +</td> +</tr> +</table> + +<table> +<tr><td><b>Overloading on a number of arguments</b></td></tr> + +<tr> +<td> + +```c +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. +} +``` + +</td> +</tr> +</table> + +(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 atop of 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 means for compile-time error reporting and debugging. With our [built-in syntax checker], macro errors should be perfectly comprehensible, enabling you for convenient development. + +[built-in syntax checker]: #q-what-about-compile-time-errors + +Currently, Metalang99 is used at [OpenIPC] as an indirect dependency of [Datatype99] and [Interface99]; this includes an [RTSP 1.0 implementation] along with ~50k lines of private code. + +[OpenIPC]: https://openipc.org/ +[RTSP 1.0 implementation]: https://github.com/OpenIPC/smolrtsp/ + +[Datatype99]: https://github.com/hirrolot/Datatype99 +[Interface99]: https://github.com/hirrolot/Interface99 + +## 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]: + +```c +#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); + } + + return -1; +} +``` + +Or [Interface99]: + +```c +#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. + +[tagged unions]: https://en.wikipedia.org/wiki/Tagged_union +[virtual method tables]: https://en.wikipedia.org/wiki/Virtual_method_table +[motivational post]: https://hirrolot.github.io/posts/macros-on-steroids-or-how-can-pure-c-benefit-from-metaprogramming.html + +## Getting started + +Metalang99 is just a set of header files and nothing else. To use it as a dependency, you need to: + + 1. Add `metalang99/include` to include directories. + 2. Specify [`-ftrack-macro-expansion=0`] (GCC) or [`-fmacro-backtrace-limit=1`] (Clang) to avoid useless macro expansion errors. + +[`-ftrack-macro-expansion=0`]: https://gcc.gnu.org/onlinedocs/gcc/Preprocessor-Options.html +[`-fmacro-backtrace-limit=1`]: https://clang.llvm.org/docs/ClangCommandLineReference.html#cmdoption-clang-fmacro-backtrace-limit + +If you use CMake, the recommended way is [`FetchContent`]: + +[`FetchContent`]: https://cmake.org/cmake/help/latest/module/FetchContent.html + +```cmake +include(FetchContent) + +FetchContent_Declare( + metalang99 + URL https://github.com/hirrolot/metalang99/archive/refs/tags/vx.y.z.tar.gz # vx.y.z +) + +FetchContent_MakeAvailable(metalang99) + +target_link_libraries(MyProject metalang99) + +# Disable full macro expansion backtraces for Metalang99. +if(CMAKE_C_COMPILER_ID STREQUAL "Clang") + target_compile_options(MyProject PRIVATE -fmacro-backtrace-limit=1) +elseif(CMAKE_C_COMPILER_ID STREQUAL "GNU") + target_compile_options(MyProject PRIVATE -ftrack-macro-expansion=0) +endif() +``` + +Optionally, you can [precompile headers] in your project that rely on Metalang99. This will decrease compilation time because the headers will not be compiled each time they are included. + +[precompile headers]: https://en.wikipedia.org/wiki/Precompiled_header + +[Tutorial](https://hirrolot.gitbook.io/metalang99/) | [Examples](examples/) | [User documentation](https://metalang99.readthedocs.io/en/latest/) + +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 their built-in deduction. Being an interpreter, 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), Metalang99's partial application allows to capture an environment by applying constant values first. Besides that, partial application facilitates better reuse of metafunctions; see `ML99_const`, `ML99_compose`, etc. + + - **Debugging and error reporting.** You can conveniently debug your macros with `ML99_abort` and report unrecoverable errors with `ML99_fatal`. The interpreter will immediately halt and do the trick. To the best of our knowledge, no other macro framework provides such a mechanism for debugging and error reporting. + +[Boost/Preprocessor]: http://boost.org/libs/preprocessor +[Order PP]: https://github.com/rofl0r/order-pp + +## 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. + +[Poica]: https://github.com/hirrolot/poica + +## 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. + +[Metalang99-compliant macros]: https://metalang99.readthedocs.io/en/latest/#definitions +[`ML99_todo` and its friends]: https://metalang99.readthedocs.io/en/latest/util.html#c.ML99_todo + +## Blog posts + + - [_Pretty-Printable Enumerations in Pure C_](https://hirrolot.github.io/posts/pretty-printable-enumerations-in-pure-c.html) + - [_What’s the Point of the C Preprocessor, Actually?_] + - [_Macros on Steroids, Or: How Can Pure C Benefit From Metaprogramming_](https://hirrolot.github.io/posts/macros-on-steroids-or-how-can-pure-c-benefit-from-metaprogramming.html) + - [_Extend Your Language, Don’t Alter It_](https://hirrolot.github.io/posts/extend-your-language-dont-alter-it.html) + +[_What’s the Point of the C Preprocessor, Actually?_]: https://hirrolot.github.io/posts/whats-the-point-of-the-c-preprocessor-actually.html + +## Contributing + +See [`CONTRIBUTING.md`](CONTRIBUTING.md). + +## Architecture + +See [`ARCHITECTURE.md`](ARCHITECTURE.md). + +## Idioms + +See [`idioms.md`](idioms.md). + +## Optimization tips + +See [`optimization_tips.md`](optimization_tips.md). + +## Release procedure + + 1. Update the `PROJECT_NUMBER` field in `Doxyfile`. + 2. Update the `release` field in `docs/conf.py`. + 3. Update `ML99_MAJOR`, `ML99_MINOR`, and `ML99_PATCH` in `include/metalang99.h`. + 4. Update the version number in `spec/spec.tex` & `spec/spec.pdf`. + 5. Update `CHANGELOG.md`. + 6. Release the project in [GitHub Releases]. + +[GitHub Releases]: https://github.com/hirrolot/metalang99/releases + +## 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`] +```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`] +```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: + +```c +// 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](https://hirrolot.gitbook.io/metalang99/testing-debugging-and-error-reporting). From my experience, 95% of errors are comprehensible -- Metalang99 is built for humans, not for macro monsters. + +### Q: What about debugging? + +A: See the chapter [_"Testing, debugging, and error reporting"_](https://hirrolot.gitbook.io/metalang99/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? + +A: + + 1. Because macro recursion is prohibited, there is an ad-hoc [recursion engine] which works by deferring macro expansions and passing continuations here and there. + 2. Upon it, the [continuation-passing style] [interpreter] reduces language expressions into final results. + 3. 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. + +[recursion engine]: include/metalang99/eval/rec.h +[interpreter]: include/metalang99/eval/eval.h +[continuation-passing style]: https://en.wikipedia.org/wiki/Continuation-passing_style + +### Q: Why not third-party code generators? + +A: See the blog post [_"What’s the Point of the C Preprocessor, Actually?"_](https://hirrolot.github.io/posts/whats-the-point-of-the-c-preprocessor-actually.html) + +### Q: Is it Turing-complete? + +A: The C/C++ preprocessor is capable to iterate only [up to a certain limit](https://stackoverflow.com/questions/3136686/is-the-c99-preprocessor-turing-complete). For Metalang99, this limit is defined in terms of reductions steps: once a fixed amount of reduction steps is 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: 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 |