8

This started out as a SO question but I realized that it is quite unconventional and based on the actual description on the websites, it might be better suited to programmers.se since the question has a lot of conceptual weight.

I have been learning clang LibTooling and it is a very powerful tool capable of exposing the entire "nitty gritty" of the code in a friendly way, that is, in a semantic way, and not by guessing either. If clang can compile your code, then clang is certain about the semantics of every single character inside that code.

Now allow me to step back for a moment.

There are many practical problems that arise when one engages in C++ template metaprogramming (and especially when venturing beyond templates into the territory of clever albeit terrifying macros). To be honest, to many programmers, myself included, many of the ordinary uses of templates are also somewhat terrifying.

I guess a good example would be compile-time strings. This is a question that is over a year old now, but it is clear that C++ as of right now does not make this easy for mere mortals. While looking at these options isn't quite enough to induce nausea for me, it nevertheless leaves me unconfident about being able to produce magical, maximally efficient machine code to suit whatever fancy application I have for my software.

I mean, let's face it, folks, strings are pretty simple and basic. Some of us just want a convenient way to emit machine code that has certain strings "baked in" significantly more than we do get when coding it the straightforward way. In our C++ code.

Enter clang and LibTooling, which exposes the abstract syntax tree (AST) of the source code and allows a simple custom C++ application to correctly and reliably manipulate raw source code (using Rewriter) alongside a rich semantic object-oriented model of everything in the AST. It handles a lot of things. It knows about the macro expansions, and lets you follow those chains. Yes, I am talking about source-to-source code transformation or translation.

My fundamental thesis here is that clang now enables us to create executables which themselves can function as the ideal custom preprocessor stages to our C++ software, and we can implement these metaprogramming stages with C++. We are simply constrained by the fact that this stage must take input which is valid C++ code and produce as output more valid C++ code. Plus whatever other constraints your build system applies.

The input has to be at least very close to valid C++ code because, after all, clang is the compiler front-end and we are just poking around and being creative with its API. I do not know if there is any provision for being able to define new syntax to use, but clearly we have to develop the ways to properly parse it and add it to the clang project in order to do this. To expect any more is to have something in the clang project that is out of scope.

Not a problem. I would imagine that some no-op macro functions can handle this task.

Another way to look at what I'm describing is to implement metaprogramming constructs using runtime C++ by manipulating the AST of our source code (thanks to clang and its API) instead of implementing them using the more limited tools available in the language itself. This has clear compilation performance benefits as well (template-heavy headers slow compilation proportionally to how often you use them. Lots of compiled stuff then gets carefully matched up and thrown away by the linker).

This does, however, come at the cost of introducing an additional step or two in the build process and also in the requirement of writing some (admittedly) somewhat more verbose software (but at least it is straightforward runtime C++) as part of our tool.

That isn't the whole picture. I am pretty certain that there is a much larger space of functionality that can be had from generating code that is extremely difficult or impossible with core language features. In C++ you can write a template or a macro or a crazy combination of both, but in a clang tool you can modify classes and functions in ANY way that you can achieve with C++, at runtime, while having full access to the semantic content, in addition to template and macros and everything else.

So, I'm wondering about why everybody isn't already doing this. Is it that this functionality from clang is so new and nobody is familiar with the huge class hierarchy of clang's AST? That can't be it.

Perhaps I am just underestimating the difficulty of this a little bit, but doing "compile-time string manipulation" with a clang tool is nearly criminally simple. It's verbose, but it's insanely straightforward. All that's needed are a bunch of no-op macro functions that map to actual real std::string operations. The clang plugin implements this by fetching all the relevant no-op macro calls, and performs the operations with strings. This tool is then inserted as a part of the build process. During build, these no-op macro function calls are automatically evaluated into their results, and then inserted back as plain old compile-time strings in the program. The program can then be compiled as usual. In fact this resulting program is also much more portable as a result, not requiring a fancy new compiler supporting C++11.

  • This is an unusually long question. Could you perhaps condense it to your most relevant points? – amon Sep 26 '14 at 7:55
  • I do post a lot of long questions. But especially with this one, all of the parts of the question are important, I think. Maybe skip the first 6 paragraphs? Haha. – Steven Lu Sep 26 '14 at 7:57
  • 3
    Sounds a lot like the syntactic macros pioneered in Lisp and recently picked up by Haxe, Nemerle, Scala and similar languages. There is quite some reading on why Lisp macros are considered harmful. Although I haven't heard a convincing argument just yet, you may well find reasons why people have been reluctant to add them to every language (besides the fact that it's not necessarily straight forward). – back2dos Sep 26 '14 at 8:13
  • Yeah its meta-ifying C++. Which can mean better, faster code. As for those languages. Well where shall I start. What's a multi-million dollar video game implemented in any of those languages? What's a modern web browser implemented in any of those languages? OS kernel? Alright, it actually seems like Haxe has some amount of traction, but you get the idea. – Steven Lu Sep 26 '14 at 8:14
  • 1
    @nwp, Well, I can't help but point out that you seem to have missed the entire point of the post. Compile-time strings is simply a most contrived and minimal concrete example of the capabilities available to us now. – Steven Lu Sep 26 '14 at 8:31
6

Yes, Virginia, there is a Santa Claus.

The notion of using programs to modify programs has been around a long time. The original idea came from John von Neumann in the form of stored-program computers. But machine code modifying machine code in arbitrary ways is pretty inconvenient.

People generally want to modify source code. This is mostly realized in the form of program transformation systems (PTS).

PTS generally offer, for at least one programming language, the ability to parse to ASTs, manipulate that AST, and regenerate valid source text. If in fact you dig around, for most mainstream languages, somebody has built such a tool (Clang is an example for C++, the Java compiler offers this capability as an API, Microsoft offers Rosyln, Eclipse's JDT, ...) with a procedural API that is actually pretty useful. For the broader community, almost every language-specific community can point to something like this, implemented with various levels of maturity (usually modest, many "just parsers producing ASTs"). Happy metaprogramming.

[There's a reflection-oriented community that tries to do metaprogramming from inside the programming language, but only achieve "runtime" behaviour modifiation, and only to the extent that the language compilers made some information available by reflection. With the exception of LISP, there are always details about the program that are not available by reflection ("Luke, you need the source") that always limit what reflection can do.]

The more interesting PTS do this for arbitrary languages (you give the tool a language description as a configuration parameter, including at a minimum the BNF). Such PTS also allow you to do "source to source" transformation, e.g., specify patterns directly using the surface syntax of the targeted language; using such patterns, you can code fragments of interest, and/or find and replace code fragments. This is far more convenient than the programming API, because you don't have to know every microscopic details about the ASTs to do most of your work. Think of this as meta-metaprogramming :-}

A downside: unless the PTS offers various kinds of useful static analyses (symbol tables, control and data flow analyses), it is hard to write really interesting transformations this way, because you need to check types and verify information flows for most practical tasks. Unfortunately, this capability is in fact rare in the general PTS. (It is always unavailable with the ever-proposed "If I just had a parser... " See my bio for a longer discussion of "Life After Parsing").

There's a theorem that says if you can do string rewriting [thus tree rewriting] you can do arbitrary transformation; and thus a number of PTS lean on this to claim you can metaprogram anything with just the tree rewrites they offer. While the theorem is satisfying in the sense you are now sure you can do anything, it is unsatisfying in the same way that a Turing Machine's ability to do anything doesn't make programming a Turing Machine the method of choice. (The same holds true for systems with just procedural APIs, if they will let you make arbitrary changes to the AST [and in fact I think this is not true of Clang]).

What you want is the best of both worlds, a system that offers you the generality of the language-parameterized type of PTS (even handling multiple languages), with the additional static analyses, the ability to mix source-to-source transformations with procedural APIs. I only know of two that do this:

  • Rascal (MPL) MetaProgramming Language
  • our DMS Software Reengineering Toolkit

Unless you want the write the language descriptions and static analyzers yourself (for C++ this is a tremendous amount of work, which is why Clang was constructed both as a compiler and as general procedural metaprogramming foundation), you will want a PTS with mature language descriptions already available. Otherwise you will spend all your time configuring the PTS, and none doing the work you actually wanted to do. [If you pick a random, non-mainstream language, this step is very hard to avoid].

Rascal tries to do this by co-opting "OPP" (Other People's Parsers) but that doesnt help with the static analysis part. I think they have Java pretty well in hand, but I'm very sure they don't do C or C++. But, its a academic research tool; hard to blame them.

I emphasize, our [commercial] DMS tool does have Java, C, C++ full front ends available. For C++, it covers almost everything in C++14 for GCC and even Microsoft's variations (and we are polishing now), macro expansion and conditional management, and method-level control and data flow analysis. And yes, you can specify grammar changes in a practical way; we built a custom VectorC++ system for a client that radically extended C++ to use what amount to F90/APL data-parallel array operations. DMS has been used to carry out other massive metaprogramming tasks on large C++ systems (e.g., application architectural reshaping). (I am the architect behind DMS).

Happy meta-metaprogramming.

  • Cool, I think Clang and DMS, while they have some overlapping capabilities, are pieces of software that are not really in the same category. I mean, one is probably ridiculously expensive and I could probably never justify the resources it'd take to gain access to it, and the other is unrestrictive free open source. This is a huge difference... Part of what gets me excited about these exciting metaprogramming capabilities is indeed the fact that it's permissible not only to use it freely but also to distribute clang based binary tools freely. – Steven Lu Sep 29 '14 at 13:25
  • Anything sold commercially is "rediculously expensive" compared to free. Raw cost isn't the issue; what matters is that for some people, the payback for acquiring the commercial product is higher than the payback for the free artifact, otherwise there would be no commercial software. This obviously depends on your specific needs. Clang is an interesting point in the tool space, and will certainly have points of useful application. I'd like to think (since I'm the DMS architect) that DMS has broader capabilities. Clang is unlikely to support languages other than C++ well, as an example. – Ira Baxter Sep 29 '14 at 13:57
  • Certainly. There is no question that DMS is incredibly powerful, almost to the point of magic (à la Arthur C. Clarke), and while clang is great, it really is just a well-written C++ frontend, of which there are many. A great many small steps forward, that it is, it still wouldn't be really fair to compare it to DMS. Alas, even with such a powerful tools at our disposal, working software does not write itself. It must still come into existence through careful translation using the tools, or (pretty much always the superior option) written fresh. – Steven Lu Sep 29 '14 at 14:08
  • You can't afford to build tools like Clang or DMS from fresh. Nor can you usually afford to throw that application you wrote with a team of 10 over 5 years. We will be needing such tools more and more often, as software sizes and lifetimes continue to grow. – Ira Baxter Sep 29 '14 at 14:13
  • @StevenLu: Well, DMS thanks you for the compliment, but there is nothing magic about it. DMS does have the benefit of almost 2 linear decades of engineering and a clean architectural platform (aw, shucks, YMMV) that has held up pretty well. Similarly, Clang has a lot of good engineering in it. I agree, they weren't designed to solve exactly the same problem ... DMS's scope is explicitly intended to be larger when it comes to symbolic program manipulation, and much smaller when it comes to being a production compiler. – Ira Baxter Sep 30 '14 at 2:40
3

Metaprogramming in C++ with compilers' API (instead of using templates) is indeed interesting and practically possible. Since metaprogramming is not (yet) standardized, you will be tied to a specific compiler, which is not the case with templates.

So, I'm wondering about why everybody isn't already doing this. Is it that this functionality from clang is so new and nobody is familiar with the huge class hierarchy of clang's AST? That can't be it.

Many people do this, but in other languages. My opinion is that most C++ (or Java, or C) developers don't see the need for it (maybe rightfully), or are not accustomized to metaprogramming approaches; I also think that they are happy with the refactoring/code-generating features of their IDE, and that anything fancier might be seen too complex/hard to maintain/hard to debug. Without proper tools, it might be true. You should also take into account inertia and other non-technical problems, like hiring and/or training people.

By the way, since we are mentionning Common Lisp and its macro system (see Basile's answer), I must say that just yesterday, Clasp was released (I am not affiliated):

Clasp intends to be a conforming Common Lisp implementation that compiles to LLVM IR. Moreover, it exposes Clang libraries (AST, Matcher) to the developer.

  • First, that means that you could write in CL and not use C++ anymore, except when using its libraries (and if you need macros, use CL macros).

  • Secondly, you can write tools in CL for your existing C++ code (analysis, refactoring, ...).

2

Several C++ compilers have some more or less documented and stable API, in particular most free software compilers.

Clang/LLVM is mostly a big set of libraries, and you could use them.

Recent GCC is accepting plugins. In particular, you could extend it using MELT (which is itself a meta-plugin, providing your with a higher-level domain specific language to extend GCC).

Notice that the syntax of C++ is not easily extensible in GCC (and probably neither in Clang), but you could add your own pragmas, builtins, attributes, and compiler passes to do what you want (perhaps also providing some preprocessor macros invoking these things to give a user-friendly syntax).

You might be interested in multi-stage languages and compilers, see e.g the Implementing Multi-stage Languages Using ASTs, Gensym, and Reflection paper by C.Calcagno et al. and work around MetaOcaml. You certainly should look inside the macro facilities of Common Lisp. And you could be interested by JIT libraries like libjit, GNU lightning, even LLVM, or simply -at run-time!- generate some C++ code, fork a compilation of it into a shared object dynamic library, then dlopen(3) that shared object. J.Pitrat's blog is also related to such reflective approaches.

  • Interesting. That is very good to see GCC continuing to evolve here. This isn't an answer that addresses anything i've asked, but I like it nonetheless. – Steven Lu Sep 26 '14 at 8:30
  • Re: your new edits... That's a good point about code rewriting itself. This does actually start to bring such meta-program capability to C++ as well, much more accessibly than before, which is also quite interesting. – Steven Lu Sep 26 '14 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.