Edoardo Vacchi on attribute grammars

I previously wrote that predictable performance is a practical challenge for using attribute grammars on real work. It does little good to quickly write the first version of a compiler pass if you then spend hours debugging oddball performance problems.

Edoardo Vacchi wrote me the following in response. I agree with him: having an explicit evaluation construct, rather than triggering attribute contributions automatically, is likely to make performance more predictable. UPDATED: edited the first paragraph as suggested by Edoardo.

Hi,

This is Edoardo Vacchi from Università degli Studi di Milano (Italy). For my PhD thesis I’m working on a language development framework called “Neverlang”[1,2]. Neverlang is an ongoing project of Walter Cazzola's ADAPT Lab; I am involved with its latest incarnation "Neverlang 2".

I stumbled upon an (old) blog post of yours about Attribute Grammars [3] and I would be interested to know if you knew some “authoritative” references that I could cite with respect to the points that you raise, with particular attention to point (3) “unpredictable performances” and, in part, to (2) caching.

The Neverlang model resembles that of simple “compiler-compilers” like Yacc, where attributes behave more like variables than functions; thus they are generally computed only once; in Neverlang attributes can also be re-computed using the `eval` construct, which descends into a child and re-evaluates the corresponding semantic action.

On the one hand, the need for an explicit `eval` make it less “convenient” than regular AG-based frameworks; on the other hand, I believe this gives better predictability, and, although the focus for the framework are not performances, but rather modularity, I think that “predictability” would better motivate the reasons for this choice.

Thanks in advance,

[1] http://link.springer.com/chapter/10.1007%2F978-3-642-39614-4_2#page-1
[2] http://dl.acm.org/citation.cfm?id=2584478
[3] http://blog.lexspoon.org/2011/04/practical-challenges-for-attribute.html

Edoardo Vacchi is PhD Student at Walter Cazzola's ADAPT-Lab, a research lab at Università degli Studi di Milano that investigates methods and techniques for programming language development and software adaptation and evolution. Walter Cazzola is associate professor at UniMi and his research is concerned with software and language engineering. More info about Neverlang can be found at the website http://neverlang.di.unimi.it.

C compilers exploiting undefined behavior

It's getting out of hand the way C compilers exploit undefined behavior. I see via John Regehr's blog that there is a SPEC benchmark being turned into a noop via an undefined-behavior argument.

This isn't what the spec writers had in mind when they added undefined behavior. To fix it, Regehr's idea of having extra checkers to find such problems is a plausible one, though it will take a dedicated effort to get there.

An easier thing to do would be for gcc and Clang to stop the madness! If they see an undefined behavior bullet in their control-flow graphs, then they should leave it there, rather than assuming it won't happen and reasoning backward. This will cause some optimizations to stop working, but really, C compilers were already plenty good 10 years ago. The extra level of optimizations is not a net win for developers. Developers want speed, sure, but above all they want their programs to do what they look like they do.

It should also be possible to improve the spec around this, to pin down what undefined behavior means a little more specifically. For example, left-shifting into the sign bit of a signed integer is undefined behavior. That's way underspecified. The only real options are: shift into the sign bit as expected, turn the integer into unpredictable garbage, or throw an exception. As things stand, a C compiler is allowed to observe a bad left shift and then turn your whole program into a noop.

Source Maps with Non-traditional Source Code

I recently explored using JavaScript source maps with a language very different from JavaScript. Source maps let developers debug in a web browser while still looking at original source code, even if that source code is not JavaScript. A lot of programming languages support them nowadays, including Dart, Haxe, and CoffeeScript.

In my case, I found it helpful to use "source" code that is different from what the human programmers typed into a text editor and fed to the compiler. This post explains why, and it gives a few tricks I learned along the way.

Why virtual source?

It's might seem obvious that the source map should point back to original source code. That's what the Closure Tools team designed it for, and for goodness' sake, it's called a source map. That's the approach I started with, but I ran into some difficulties that eventually led me to a different approach.

One difficulty is a technical one. When you place a breakpoint in Chrome on a file mapped via a source map, it places one and only one breakpoint in the emitted JavaScript code. That works fine for a JavaScript-to-JavaScript compiler, but I was compiling from Datalog. In Datalog, there are cases where the same line of source code is used in multiple places in the output code. For example, Datalog rules are run in two different modes: once during the initial bootstrapping of a database instance, and later during an Orwellian "truth maintenance" phase. With a conventional source map, it is only possible to breakpoint one of the instances, and the developer doesn't even know which one they are getting.

That problem could be fixed by changes to WebKit, but there is a larger problem: the behavior of the code is different in each of its variants. For example, the truth maintenance code for a Datalog rule has some variants that add facts and some that remove them. A programmer trying to make sense of a single-stepping session needs to know not just which rule they have stopped on, but which mode of evaluation that rule is currentlty being used in. There's nothing in the original source code that can indicate this difference; in the source code, there's just one rule.

As a final cherry on top of the excrement pie, there is a significant amount of code in a Datalog runtime that doesn't have any source representation at all. For example, data input and data output do not have an equivalent in source code, but they are reasonable places to want to place a breakpoint. For a source map pointing to original source code, I don't see a good way to handle such loose code.

A virtual source file solves all of the above problems. The way it works is as follows. The compiler emits a virtual source file in addition to the generated JavaScript code. The virtual source file is higher-level than the emitted JavaScript code, enough to be human readable. However, it is still low-level enough to be helpful for single-step debugging.

The source map links the two forms of output together. For each character of emitted JavaScript code, the source map maps it to a line in the virtual source file. Under normal execution, web browsers use the generated JavaScript file and ignore the virtual source file. If the browser drops into a debugger--via a breakpoint, for example--then it will show the developer the virtual source file rather than the generated JavaScript code. Thus, the developer has the illusion that the browser is directly running the code in the virtual source file.

Tips and tricks

Here are a few tips and tricks I ran into that were not obvious at first.

Put a pointer to the original source file for any code where such a pointer makes sense. That way, developers can easily go find the original source file if they want to know more context about where the code in question came from. Here's the kind of thing I've been using:

    /* browser.logic, line 28 */

Also, for the sake of your developers' sanity, each character of generated JavaScript code should map to some part of the source code. Any code you don't explicitly map will end up implicitly pointing to the previous line of virtual source that does have a map. If you can't think of anything to put in the virtual source file, then try a blank line. The developer will be able to breakpoint and single-step that blank line, which might initially seem weird. It's less weird, though, than giving the developer incorrect information.

Name your JavaScript variable names carefully. I switched generated temporaries to start with "z$" instead of "t$" so that they sort down at the bottom of the variables list in the Chrome debugger. That way, when an app developer looks at the list of variables in a debugger, the first thing their eyes encounter are their own variables.

Emit variable names into the virtual source file, even when they seem redundant. It provides an extra cue for developers as they mentally map what they see in the JavaScript stack trace and what they see in the virtual source file. For example, here is a line of virtual source code for inputting a pair of values to the "new_input" Datalog predicate; the "value0" and "value1" variables are the generated variable names for the pair of values in question.

    INPUT new_input(value0, value1)

Implementation approach

Implementing a virtual source file initially struck me as a cross-cutting concern that was likely to turn the compiler code into a complete mess. However, here is an approach that makes it not so bad.

The compiler already has an "output" stream threaded through all classes that do any code generation. The trick is to augment the class used to implement that stream with a couple of new methods:

• emitVirtual(String): emit text to the virtual source file
• startVirtualChunk(): mark the beginning of a new chunk of output

With this extended API, working with a virtual source file is straightforward and non-intrusive. Most compiler code remains unchanged; it just writes to the output stream as normal. Around each human-comprehensible chunk of output, there is a call to startVirtualChunk() followed by a few calls to emitVirtual(). For example, whenever the compiler is about to emit a Datalog rule, it first calls startVirtualChunk() and then pretty prints the code to the emitVirtual() stream. After that, it emits the output JavaScript.

With this approach, the extended output stream becomes a single point where the source map can be accumulated. Since this class intercepts writes to both the virtual file and the final generated JavaScript file, it is in a position to maintain a mapping between the two.

The main downside to this approach is that the generated file and the virtual source file must put everything in the same order. In my case, the compiler is emitting code in a reasonable order, so it isn't a big deal.

If your compiler rearranges its output in some wild and crazy order, then you might need to do something different. One approach that looks reasonable is to build a virtual AST while emitting the main source code, and then only convert the virtual AST to text once it is all accumulated. The startVirtualChunk() method would take a virtual AST node as an argument, thus allowing the extended output stream to associate each virtual AST node with one or more ranges of generated JavaScript code.

Practical challenges for attribute grammars

I've had occasion recently to work on a compiler implemented with an attribute grammar framework. Such frameworks let you declare attributes on AST nodes that are computed in terms of other attributes. In general, it's a powerful and convenient way to compute information about an AST, and I expect they make a lot of sense in tools that only analyze ASTs and don't generate or rewrite them. They save you from working out a specific computation order, because the tool can look at which attributes refer to which other ones and compute them all on demand.

For compilers, however, I no longer think attribute grammars work well. Let me describe three fundamental problems with attribute grammars for use in compilers.

1. Attributes can be inherited, meaning they look up in the AST to for information. Examples are the expected type of an expression, the enclosing module for any node, and the set of free variables available in some context. These computations cannot be computed unless the node in question really is attached to an AST. However, compilers create new AST nodes all the time, and while those new nodes are being set up, they can't possibly be attached yet. Thus, unattached nodes are inconsistent with inherited attributes.
   
   
2. Compilers change the AST. They desugar syntax into lower-level syntax, they optimize, they reorder parts of the program, and so on. Every time the AST changes, some cached attribute values become invalid. At that point, how do you flush the caches that are now invalid? To some extent you can get by by flushing all caches after every compiler phase. However, this means that later parts of a phase will see stale data compared to earlier parts. This situation results in bugs where, to fix them, you have to reason about the exact order that the traversal happens and the relationship of the stale data to the current version of the AST.
   
   
3. Attributes have unpredictable performance characteristics. When you see a reference to an attribute, it might be cached and take constant time. On the other hand, it might trigger a chain of attribute computations that chain across the whole program. It's much harder to convince yourself that a particular AST traversal will operate in linear time, because you don't know how expensive all the attribute computations are.
   

These are all potentially addressable, but they are serious challenges that any practical tool will need to face. As things stand, I haven't seen an attribute grammar framework that is there yet. They don't really achieve their main benefit, which is to save you from reasoning about order of evaluation of and dependencies between different attributes. You end up reasoning about them anyway to get the bugs out and the performance up.

Instead of storing attributes on the AST nodes and computing them with an attribute grammars framework, a more traditional approach is as follows. Store a few, carefully selected bits of information on nodes, such as the types of expressions. These things must be carefully maintained across all AST rewrites, and the compiler will be buggy if you get it wrong, so don't store too much this way. For most information, have each compiler phase compute and maintain whatever information it needs. This results in some amount of computation, but you can usually find a way to calculate whatever you need in linear time. Since any one phase will usually require at least linear time, anyway, this is sufficient for getting the compiler reasonably performant before you do your first profile run.