As i was saying last time, the nice thing about “no backtracking” is that it makes the language much easier to understand. Simple rules benefit both the compiler and the code reader; both are attempting to read the code to make sense of it. It is not always a good idea to take advantage of the compiler’s ability to search a large space if that makes it harder for a human to understand the code.

Suppose you have something like this mess: (*)

namespace XYZ.DEF
{ 
    public class GHI {} 
} 
namespace QRS.DEF.GHI 
{ 
    public class JKL { } 
} 

… in another file …

using QRS; 
namespace TUV  
{
    using XYZ;
    namespace ABC
    {
        namespace DEF
        {
            class GHI { }
            class MNO : DEF.GHI.JKL { }
        }
    }
} 

And now we must work out the base type of MNO.

With no backtracking we say “The nearest container of MNO that has a member DEF is ABC, therefore DEF means ABC.DEF”. Therefore GHI is ABC.DEF.GHI. Therefore JKL is ABC.DEF.GHI.JKL, which does not exist, therefore, give an error. The developer must fix the error by giving a type name that lets the compiler identify which DEF you meant.

If we had backtracking, what would we have to do? We’d get that error, and then we’d backtrack. Does XYZ contain a DEF? Yes. Does it contain a GHI? Yes. Does it contain a JKL? No. Backtrack again. Does QRS contain an DEF.GHI.JKL? Yes.

That works, but can we logically conclude from the fact that it works that it is the one the user meant?

Who the heck knows in this crazy situation? We got all kinds of good bindings in there that then went bad very late in the game. The idea that we stumbled upon the desired answer after going down so many blind alleys seems highly suspect. Maybe there is yet another choice in there that is the one the user meant. We cannot know that unless we try all of them, and again, that could involve a lot of searching.

The correct thing to do here is not to backtrack multiple times and try out all kinds of worse bindings for every stage of the lookup. The correct thing to do is to say “buddy, the best possible match for this lookup gives nonsensical results; give me something less ambiguous to work with here please.”

An unfortunate fact about writing a language where the compiler by design complains loudly if the best match is something that doesn’t work, is that developers frequently say “well, sure, in general I want the compiler to point out all my mistakes — or, rather, all my coworker’s mistakes. But for this specific case, I know what I am doing, so please, compiler, do what I mean, not what I say.”

Trouble is, you can’t have it both ways. You can’t have both a compiler that both enforces rigid rules that make it highly likely that suspicious code will be aggressively identified as erroneous and allow crazy code via compiler heuristics that figure out “what I really meant” when you write something that the compiler quite rightly sees as ambiguous or wrong.

I could discuss many more places where we could do backtracking but do not. Method type inference, for example, always either makes progress or fails; it never backtracks in C# (**). But I think I will leave it at that. Except to say that there is one place where we do use backtracking, and that’s analysis of overload resolution in nested lambdas. I wrote about that here.

(*) When reading this remember that in C#, “namespace XYZ.DEF { }” is a short form for “namespace XYZ{ namespace DEF { } }”

(**) Unlike in, say, F#.

---

Commentary from 2021:

There were a number of good comments to the original post, which pointed out:

• Error analysis often has to perform some sort of backtracking to give a good error. In the examples I gave, for instance, we could run a backtracking analysis and then give a “did you mean…?” style error message if backtracking finds a solution, and a different error if no solution can be found. That’s a great idea in principle, but in practice we often end up in situations where backtracking is expensive, so we’d want to put a box around the amount of time and resources the error reporting system uses.
• This is even more the case when IntelliSense is involved. IntelliSense by definition is typically operating on code that is wrong; if the code was right, why are you editing it? IntelliSense needs to give good options, but it needs to do so in under 30 milliseconds, so it uses lots of tricks to meet its time budget.
• There was also some good discussion of the deeper language design point here. There are times when we want to use backtracking algorithms, and times we do not; what motivates that choice? There is not just one thing; like all design and implementation problems it comes down to resolving conflicts between incompatible principles. One of the nice things about “no backtracking” algorithms is that they often allow “local” analysis; if we see ABC.DEF.GHI and immediately after, ABC.DEF.XYZ, we know that no matter what, the ABC.DEF means the same thing; the meanings of ABC and ABC.DEF do not change depending on whether GHI and XYZ produce errors or not. That’s a nice property to have.

A number of the articles I’ve published over the years involve “backtracking” algorithms; most recently my series on how to solve Sudoku puzzles (and more generally, all graph colouring problems) by backtracking. The idea of a backtracking algorithm is really simple and powerful: when faced with a choice, try every possibility. If all of them go wrong, backtrack to the previous choice and try a different possibility. Backtracking algorithms are essentially a depth-first search of the space of possible solutions.

But what if the solution space is large? There are more ways to fill in nine digits in 81 places than there are protons in the entire Universe; we can’t check them all. The reason that backtracking works so rapidly for Sudoku puzzles is because typically every guess eliminates many of the branches of the solution tree. If you guess that the first square is 1 then you do not need to explore the possibility that the second square is 1; you can just prune that branch and never explore it. Since that branch itself is vast, that’s a good strategy! (There are pathological cases for this algorithm, but in practice it is fast.)

Backtracking algorithms work well for many situations, but we have consciously eschewed them in the design of C#. (With a few exceptions). For example, there is no backtracking that ever crosses “phases” of compilation in C#.(*) When we are presented with some source code the first thing we do is “lex” it; break it up into “tokens”. This is akin to finding the words in a sentence by looking at the spacing and punctuation. Then we do a grammatical analysis of the token stream, and then we do a semantic analysis of the grammatical analysis. When one of those phases finds an error, we never backtrack to a previous phases and ask for more analysis. Suppose for example you have this silly code:

x = j+++++1;

That is lexically correct C# code. The lexer is a greedy lexer; it tries to make the largest token it can at any given time. So it tokenizes this as:

x = j ++ ++ + 1 ;

Now the grammar analyzer takes that token stream and says “this is an expression involving two identifiers, one constant and four operators; how should I parenthesize that?” The grammar analyzer determines using the rules of precedence and associativity that this means

x=(((j++)++)+1);

So this means “evaluate x, then increment j, then increment whatever the previous result was, then add 1 to the previous result, then assign the previous result to x, done”

Then the semantic analyzer checks that to make sure that all those operations make sense. They do not, because the result of j++ is a value, not a variable, but the second ++ requires a variable. The semantic analyzer gives an error, and the program does not compile.

If we had a backtracking compiler, the semantic analyzer could tell the parser “no, you did something wrong, give me a different parse tree if there is one”.

Suppose the parser does that. It could say well, maybe that last + was not a binary operator but rather the unary operator + applied to 1, oh, but if we do that then we have two expressions next to each other with no intervening operator. Same thing if the second ++ applies to the +1 instead of the j++. So no, there is no other parse of this. So push back on the lexer and ask it to backtrack.

The lexer could then say, oh, sure, if you don’t like that then maybe my guess that the second ++ was ++ was wrong. Try this one:

x = j ++ + ++ 1 ;

and then the parser says OK, if that’s where the token breaks are then the grammatical analysis is:

x=((j++)+(++1));

and the semantic analyzer determines that’s wrong too, this time because you can’t have a ++ on a constant. So the semantic analyzer tells the parser, no, that’s not it either, and the parser tells the lexer, no, that’s not it either. And the lexer says “well, maybe that wasn’t a ++ at all the second time, maybe that should be

x = j ++ + + + 1 ;

And now the parser says “oh, I see what that is, it is two unary plus operators applied to 1 and an addition operator:

x=((j++)+(+(+1)));

and the semantic analyzer says “finally! something I can work with.”

That’s not what we do. This is a silly example, but perhaps you can see that there are two major problems with this strategy.

First, though most of the time lexing is unambiguous, in some pathological cases there are potentially enormously many ways that simple programs could be lexed. Just determining where the breaks could go between five plus signs gives eight possibilities; it grows exponentially from there. Since most of the time programs lex unambiguously, and when they do lex ambiguously, the space to explore could be really big, it’s better to always lex greedily and not backtrack ever. If a program fails grammatical analysis because of an unintended lexical structure then the best thing to do is tell the user and they’ll fix it.

The second major problem is that when backtracking, how do you know which backtracking is better? Of those eight possibilities, two give program fragments that pass semantic analysis: the one we just found, and x=(j+(+(+(+(+1))))); Is it at all clear which of the two possibilities is the one the user meant when they wrote this ridiculous statement? Remember, we’re not trying to solve a Sudoku puzzle here, where any given combination of numbers is as meaningless as the next; we are attempting to output IL that has the same meaning as the meaning intended by the user! One of these possibilities mutates j and the other does not, so it makes a difference. C# is not a “guess what you meant” language, it’s a “do what you said” language(**). If what you said was ambiguous, we should tell you about it.

---

Next time on FAIC: we’ll return to this point by looking at how the name resolution algorithm also does not backtrack.

(*) Unlike JavaScript, interestingly enough. The ECMAScript specification notes that there are lexical ambiguities involving the / character; it could be introducing a comment as // or as /*, or closing a comment as */, or could be a normal division operator, or a /= operator, or opening or closing a regular expression. Some of those overlap; The spec actually says that the correct lex is the one that produces a grammatically sensible program!

(**) Again, unlike JavaScript.

---

Commentary from 2021:

There were a lot of good comments (and some needlessly pedantic comments, imagine that) on the original article that went down a few ratholes mentioned above:

• There were some points made about the difficulty of having lexical ambiguities involving the / symbol in JS that are exacerbated by automatic semicolon insertion
• Some readers pointed out that sudoku puzzles are required by the rules of the puzzle to have a unique solution; though that is true, I was just using it as an example of a problem amenable to a backtracking algorithm; I was not intending to draw a deeper analogy between solving sudoku puzzles and building a compiler. (Fun fact though: it is possible to encode a sudoku puzzle into a C# program such that the compiler is required to find a solution or produce an error if the puzzle is ambiguous or unsolvable.)
• Some readers asked about scenarios that involve a kind of backtracking in the parser, but not “across phases”. For example, consider: (T)-1 — does that parse as a subtraction or as a cast of -1? Or my favourite: A(B<C,D>(E)) which parses as two arguments to A in C# 1, and one in C# 2. In both these situations the parser is required to “look ahead” arbitrarily far in the token stream to determine how the parse works; most of the time the parser only has to look ahead one token to determine what the parse should be. A “look ahead” and a “backtrack” are kinda sorta the same thing. Similarly there are scenarios where it is not clear whether >> is a shift operator or the end of a nested generic type.

In 2016 I worked on rearchitecting the Hack parser; Hack is a gradually-typed variant of PHP used inside Facebook. One of the major difficulties I faced in writing a purely functional, full-fidelity Hack parser is that Hack has XML literals in the language, much like VB. The lexical and grammatical rules of the language are completely different inside these XML regions and I did end up having to build some cross-phase backtracking into the parser, which was quite vexing.