Lambda the Ultimate

I know that PLT has done some work on tracking errors back to their source across macro transformers and the like.

I expect you'll need to include a lot more metadata in your processing, which might mean avoiding text->text translations and instead using a more structured model after parsing (i.e. ASTs).

You should make sure that your desugaring code never generates erroneous output. If there is an error in the input, it should be reported directly rather than being passed through to the next level. If the second stage sees bad syntax, that counts as a bug in the first stage.

Looking at the feedback I'm getting, it seems I ought to discard the separate desugarer and make the existing reader able to read the same AST node in different ways. EG, it would read the Accessor node as either (access m:b a) or a.b. This will complect the reader code, but I don't yet see a reasonably easy solution to the problems caused by intermediate textual transformation.

In the compilers/interpreters I've written, I leave open a position for term annotation. For example:

data Term a = Const a C | Var a V | App a (Term a) (Term a) | ...

The parser adds an annotation with source information (i.e.: it produces 'Term (Filename, (Lineno, Colno), (Lineno, Colno))' values). However, desugar phases (or any stage of compilation really) just blindly copy that annotation from the source terms from which they are derived.

The way I did, and I have no idea whether it's the best approach, is to include position information in the AST. Your transformations, the desugaring, should then carry the position information correctly over to the simplified AST such that, whenever a semantical error occurs, the position in the original source can be reported.

In this manner, with desugaring, you lose the ability to present nice beautified AST nodes for error reporting (since the that will very likely not represent the original AST well), but you keep the ability to point at the correct place in the source where the error occurred.

Rather than extending the AST with meta-data, a possibility I was pursuing a few years ago focuses on use of functions for annotations. An example function looks like:

anno :: a -> b -> b
anno _ x = x

That is the runtime semantics, but the annotation function allows us to carry an extra `a` value in the source tree, which can be processed in a dedicated manner.

I can go many ways with this - either create dedicated annotation functions for certain types of data (like code position) or use `anno` for everything but specialize data types based on the purpose of each annotation. I figured annotations would be used for other things, such as comments and optimization or parallelization hints.

With a few tweaks, annotations could also be modeled with monads or arrows. E.g. a monadic approach might update an abstract register with data about location in code, or treat this as generating a stream of meta-data while running the code. An arrows approach would have some advantage in supporting a more static analysis of metadata.

When you try to track source refs across things like macros expansions, inlining or other such like things, you will often find yourself asking: which of the two source references should I keep?

The general answer to this question is: both, and of course the general result is at least a list. Clearly you must do this to explain a simple chain of inline function expansions, since the compiler cannot know which call site the user thinks an error is located at: invariably it will never be the very lowest level and the top level is nonsense since it the whole program.

I have some interesting ideas here. One is this: lay down a function with parameter replacement, and you get two sets of references which themselves are far apart. First, you replace all close references with a nice range, so now you have exactly two in the expression. Then you extract the two ranges, combine them so one can distinguish caller and callee, and relabel all the terms with the combined reference.

Another technique I am thinking to implement is to maintain a reference stack, this is the static analogue of the backtrace a debugger gives at run time. You add "begin function f" and "end function f" at the start and end of every function, and after inline expansion you have a way, given a point in the code, to look back to find how that piece of code got where it is.

Most C compilers already do exactly this to trace #include files, so the technique isn't new.

Whatever method you use for reference tracking, consider that you must report locations not only for compile time errors, but also run time ones. Its not much use seeing "match failure" without a reference indicating which match failed!

So actually I suggest two methods: some "in AST" references which merge low level parametric replacements with their contexts, and, a higher level representation such as the begin/end annotations, which requires some scanning to calculate. Whatever you do, tracking source reference is a lot of work, hard to get right, and will cost a substantial fraction of your compile times .. too bad: most compiles fail, so generating good code is far less important than reporting on bad stuff :)

I've written an article a while ago about patching Python tracebacks. It relies on two properties of the runtime: 1) tracebacks can be fully examined, 2) error reporting can be customized ( assigning a handler to sys.excepthook in the Python case ).

The algorithm maps line information of the transformation target code Q onto the original user written code P. The central idea goes like this.

Suppose T is the failure token in TQ which is the token-sequence of Q and V is the string value of that token. We want to determine where T comes from in TP. If T doesn't have a pre-image T' in TP because the value V doesn't exist in P we can also examine a neighbor of T.

Assume now that V exists in P. There may be n candidates for T' in TP. For each of those candidates we select a small token sequence in TP of length k ( e.g. k = 7 ) with T' in the center ( if possible ). We do the same with the error token T in TQ. In the next step we create strings from those token sequences beginning with the sequence associated with T, say ST. Those strings can be easily compared using the Levenshtein distance. The string ST' in P with the minimal edit distance to ST wins.

Actually it is a little more complicated, not only because there may still be many candidates for the optimal ST' but some of those candidates fit much better with another token X in P which has also the string value V. So one rather attempts to find an optimal mapping of sets of token in Q having value V onto sets of token in P with the same value. For more details I recommend taking a look at the article.

The algorithm is relatively robust with respect to elisions and loss of token information and the insertion of syntactical debris like delimiters. It is not language specific, doesn't hack symbol tables and stays apart from atrocities like retrofitting lexical information into AST's where it has been removed when AST's where created from parse trees.