Consider code coverage (as a code generation technique)

[masak]

I was just reading details of how Istanbul.js instruments source code to emit coverage information on a side channel, and it's pretty fascinating. (That file details how to go through a JavaScript compunit's AST and insert "counter increments" (per statement, function, and branch) — all without disrupting things like source code location, of course.)

There is something there which concerns us macro-aficionados. I would say the technique sits somewhere between a custom language, a custom backend, and full-program AST transformation. Also related somehow to the staged-languages discussion of #555.

[masak]

To make this concrete, I also enjoyed how the test specifications are laid out: small code examples, checking coverage of lines/statements/functions/branches. Extra nice is that the focus is on the API-level expectations (BDD-style), and not on low-level implementation details.

[masak]

There's a clear connection here between the kind of "invisible code injection" we want to do here, and the one discussed in #417. I could even see cases where one would like to do both of them at once on the same code base (without coordinating or even being aware of each other, and getting the right result regardless of order). This maybe suggests some constraints on the shape of the API in question.

[masak]

I thought of another alluring example (which might belong in a separate issue, except it feels like it shares and highlights the same general technique): I have a private repository called bel-tarjans-algorithm. (Haven't implemented it yet.) One thing one would likely want to do with such an piece of code would be to instrument it so that when one later ran or stepped through the code, the operated-on graph could be visualized, annotated with data local to the algorithm.

The main point is to not change the code written without a visualization in mind. In fact, either instrumentation would work, or perhaps using a different evaluator. I'm undecided on which one is preferable; maybe each has its own advantages. Perhaps extra thought need to be spent to uphold the illusion of the instrumented code supporting the full gamut of debugging (such as "step into"), but still fully giving the impression of running the original code. In that sense, the instrumented code is invisible to the debugger.

[masak]

Just found this quote:

This paper proposes that the distinguishing characteristic of Aspect-Oriented Programming
(AOP) systems is that they allow programming by making quantified programmatic assertions
over programs written by programmers oblivious to such assertions.

Feels relevant.

[masak]

The thing I would like to capture here is this: when we are authoring the instrumentation code, we are basically visiting the nodes of interest and injecting the non-invasive code. The most natural thing to do would probably be to just write the code we want, as quasi blocks, and inject it manually. But the references to data structures (for collection) in the visitor-level code would be secretly rewritten along the way to instead refer to the corresponding data structures (which would also be injected, implicitly) in the instrumented program.

[masak]

This paper uses the code injection technique on quite an impressive scale: it injects pre- and post-conditions in the right place in the program. But then it also creates entire parallel pre/post class hierarchies to mirror the ones already in the program, in order to capture that method dispatch is late-bound; finally, if the pre- and post-conditions tested fail in a certain way that violates the Liskov substitution property, a "hierarchy error" is signaled at runtime. All of this is proven to have no semantic effect on the original program, as long as the pre- and post-conditions are themselves side effect free.

[masak]

From this HN discussion:

For those not in the know, AOP is basically the Intercal COME FROM statement (itself a pun on goto, ie it's a jump but in the opposite direction) (think that through a bit). Yes, that's a totally nuts idea, but it turns out that with a bit of effort you can formulate it in such a way that you can do conference talks about it and people nod and think "o wow nice I gotta tell the team".

That's a funny/cynical way to put what this technique does. I feel though that there is (or ought to be) some kind of "safety property" involved, some kind of generalization of "injecting non-invasive code" described above.

There's also a super-interesting kind of duality here between hijacking/modifying the evaluator (the runtime approach) and hijacking/modifying the source code (the static approach).

[masak]

Put it like this. Take the concept of "slicing", wherein you can turn a program into a smaller program by keeping only a subset of the variables in it. I think the AOP safety property can be expressed in terms of this: that the "original slice" of the program still behaves the same after the code injection — proximally, because the extending slice only does side-effect-free mutations to "private" data; gensym'd variables that the original slice has no way to see or interact with.

[masak]

I hadn't heard about Meta-AspectJ before, but it seems to be playing around in this issue's ballpark.