I got a phone call from a colleague the other day asking for advice on a live consulting session at a client site. The problem description (amended to prevent information disclosure) went something like this:
We’re implementing a service that manages a set of physical backup devices. There is a set of conveyor belts with intersections and robot arms that manipulate backup tapes across the room. The service gets requests such as “transfer a fresh tape X from storage cabinet 13 to backup cabinet 89, and make sure to pass through formatting computer C or D”.
When the system starts, we calculate all shortest routes from every cabinet to every other cabinet, including special requests such as going through a particular computer. This information is stored in a large hashtable indexed by route descriptions and with routes as values.
System startup with 1,000 nodes and 250 intersections takes more than 30 minutes, and memory consumption reaches a peak of approximately 5GB. This is not acceptable.
This is the classical All-Pairs-Shortest-Paths problem on graphs. We need to find efficiently the shortest path from every vertex to every other vertex, and to store this information in a compact form; the naive solution of finding and storing every possible route using DFS or similarly simple graph searches will not yield acceptable results.
First, observe that there is no need to store route information for nodes that are not intersections. If the only edge from A is to B and the only edge from B is to C, then the route A—>B—>C does not require three pieces of data to be stored—when reaching B, there is no choice where to proceed. In other words, the nodes of our graph should be only the intersections, vertices that have fan-out higher than 2.
Next, note that the additional constraints on a route don’t pose any additional difficulty. If we need the shortest path from A to B going through C, then we really need the shortest path from A to C and then the shortest path from C to B.*
Now we’re ready to discuss the algorithm itself (Floyd-Warshall algorithm). It uses an idea very similar to the previous paragraph—if we are looking for the shortest path from A to B, then suppose this path contains a vertex V. The shortest path from A to B that goes through V consists of the shortest path from A to V and the shortest path from V to B; this is the basis of a recursive formula that enumerates the possible paths. What we need to do is consider all possibilities for V—all possible intermediate vertices. One way to do this is to number the vertices from 1 to n. Now, we can use the following recursive formula for SP(i, j, k), the length/cost** of the shortest path from vertex i to vertex j and using only the vertices 1,…,k:
SP(i, j, k) = min { SP(i, j, k-1), SP(i, k, k-1) + SP(k, j, k-1) }
(If there is an edge from i to j, we also need to consider this as a possibility in the minimum calculation.)
Finding all values of SP(i, j, k) for all the vertices and values of k from 1 to n will yield the costs of the shortest paths between every two vertices in the graph. For example, the cost of the shortest path from i to j is given by finding the minimum of SP(i, j, k) for all values of k.
Although this recursive formula looks very expensive—there are three recursive calls at each level, which leads to exponential running time—we can employ memoization for the recursive calls, i.e. store somewhere the intermediate return values of SP instead of calculating them over and over again. The amount of storage required for storing these results (naively) is n3, which is pretty bad. However, it’s fairly obvious that we don’t actually need SP(i, j, k) for all values of k—we need at each iteration (of k) to store only the minimum value obtained so far, bringing down the amount of storage to n2, which is downright amazing.
What’s even more amazing is the algorithm’s running time—all we need is n3 iterations and we have the cost of the shortest path between every two vertices in the graph!
What about storing the path itself? This is a trivial modification to the algorithm—we can use an additional matrix of size n2, and store in it for each pair (i, j) the vertex x to which we should proceed if we want to find the shortest path*** from i to j.
Translating this thing to C# is easy, and so is reconstructing the path given the data described above.
short[] vertices = g.Vertices.ToArray();
int N = vertices.Length;
_costs = new float[N,N];
_next = new short[N,N];
for (short i = 0; i < N; ++i)
{
for (short j = 0; j < N; ++j)
{
_costs[i, j] = g.EdgeCost(i, j);
if (!float.IsPositiveInfinity(_costs[i, j]))
_next[i, j] = -1;//Marker for direct edge
}
}
for (short k = 0; k < N; ++k)
{
for (short i = 0; i < N; ++i)
{
for (short j = 0; j < N; ++j)
{
if (_costs[i,k] + _costs[k,j] < _costs[i,j])
{
_costs[i, j] = _costs[i, k] + _costs[k, j];
_next[i, j] = k;
}
}
}
}
public string GetPath(short src, short dst)
{
if (float.IsPositiveInfinity(_costs[src, dst]))
return "<no path>";
short intermediate = _next[src, dst];
if (intermediate == -1) //Marker for direct edge
{
return "->"; //Direct path
}
return GetPath(src, intermediate) +
intermediate +
GetPath(intermediate, dst);
}
On my desktop PC, with an average fan-out of 3 edges from each node and 300 nodes, constructing the full set of paths took 3 seconds. Spitting out 100,000 paths took 120 milliseconds. The memory utilization was 600 KB, including storage for the graph itself.
There’s plenty of additional optimization to do here—and indeed there are graph libraries like QuickGraph that thrive on implementing and optimizing such algorithms—but in view of the above results, I felt no need to explore these additional options.
* If there were a path P from A to B going through C that did not use Q1, the shortest path from A to C and then Q2, the shortest path from C to B, then we can break P into two parts—P1, the part of P from A to C and P2, the part of P from C to B. If P1 is not Q1, then we can improve P by replacing P1 by Q1; similarly, if P2 is not Q2, then we can improve P by replacing P2 by Q2. In either case, this is a contradiction to the assumption that P was the shortest path.
** It’s trivial to adapt the algorithm so that it works for weighted edges, and indeed in our case it may be necessary to accommodate for conveyors that consume additional energy, conveyors that become packed, etc. by assigning them a weight function.
*** Again, we use the property that every path from i to j through x uses the shortest path from i to x and the shortest path from x to j.
That’s it. We’re ready for the full BNF of the Jack grammar, followed by the top-down parser of a complete Jack program. Here goes:
class ::= class cls-name { cls-var-decl* sub-decl* }
cls-var-decl ::= ( static | field ) type var-name
( , var-name )* ;
type ::= int | char | boolean | cls-name
sub-decl ::= ( constructor | function | method )
( void | type ) sub-name
'(' param-list ')' sub-body
sub-body ::= { var-decl* statement* }
var-decl ::= var type var-name ( , var-name )* ;
statement ::= let-stmt | if-stmt | while-stmt |
do-stmt | return-stmt
let-stmt ::= let var-name ( [ expr ] )? = expr ;
if-stmt ::= if '(' expr ')' { statement* }
( else { statement* } )?
while-stmt ::= while '(' expr ')' { statement* }
do-stmt ::= do sub-call ;
return-stmt ::= return expr? ;
The rest is expr (expression) and sub-call, which we’ve already seen. Generating a parser for the above BNF is trivial, much easier than what we did with expressions:
private void ParseClass()
{
Match(new Token(TokenType.Keyword, "class"));
Token className = NextToken();
if (className == null)
Expected("class name");
if (className.Type != TokenType.Ident)
Expected("identifier");
_currentClassName = className.Value;
_codeGenerator.BeginClass(className.Value);
Match(new Token(TokenType.Symbol, "{"));
ParseClassVarDecls();
ParseSubDecls();
Match(new Token(TokenType.Symbol, "}"));
_codeGenerator.EndClass();
_currentClassName = String.Empty;
_classSymTable.Clear();
}
private void ParseClassVarDecls()
{
while (IsNextTokenClassVarDecl())
{
ParseClassVarDecl();
}
}
private void ParseClassVarDecl()
{
Token varKind = NextToken();
bool isStatic = varKind.Value == "static";
Token varType = NextToken();
Token varName = NextToken();
do
{
if (isStatic)
{
Symbol variable = new Symbol(
varType.Value, varName.Value,
SymbolKind.Static, _currentClassName);
_classSymTable.AddSymbol(variable);
_codeGenerator.StaticDeclaration(variable);
}
else
{
Symbol variable = new Symbol(
varType.Value, varName.Value,
SymbolKind.Field, _currentClassName);
_classSymTable.AddSymbol(variable);
_codeGenerator.FieldDeclaration(variable);
}
} while (LookAheadToken.Value == ",");
Match(new Token(TokenType.Symbol, ";"));
}
private void ParseSubDecls()
{
while (IsNextTokenSubDecl())
{
ParseSubDecl();
}
}
private void ParseSubDecl()
{
Contract.Requires(IsNextTokenSubDecl());
Token subKind = NextToken();
Token returnType = NextToken();
Token subName = NextToken();
if (subKind.Type != TokenType.Keyword ||
!new[]{"constructor", "method", "function"}
.Contains(subKind.Value))
{
ThrowCompilationException(...);
}
if (returnType.Type != TokenType.Keyword &&
returnType.Type != TokenType.Ident)
{
ThrowCompilationException(...);
}
if (subName.Type != TokenType.Ident)
{
ThrowCompilationException(...);
}
_currentSub = new Subroutine(
(SubroutineKind) Enum.Parse(typeof (SubroutineKind),
subKind.Value, ignoreCase: true),
_currentClassName, subName.Value, returnType.Value);
if (_currentSub.Kind == SubroutineKind.Constructor &&
_currentSub.ReturnType != _currentClassName)
{
ThrowCompilationException(...);
}
Match(new Token(TokenType.Symbol, "("));
ParseFormalParamList();
Match(new Token(TokenType.Symbol, ")"));
ParseSubBody();
_currentSub = null;
_methodSymTable.Clear();
}
private void ParseFormalParamList()
{
while (LookAheadToken.Value != ")")
{
Token paramType = NextToken();
Token paramName = NextToken();
if (paramType.Type != TokenType.Keyword &&
paramType.Type != TokenType.Ident)
{
ThrowCompilationException(...);
}
if (paramName.Type != TokenType.Ident)
{
ThrowCompilationException(...);
}
Symbol parameter = new Symbol(paramType.Value,
paramName.Value, SymbolKind.Parameter,
_currentClassName);
_currentSub.Parameters.Add(parameter);
_methodSymTable.AddSymbol(parameter);
if (LookAheadToken.Value == ",")
{
NextToken();//Skip the comma
}
}
}
private void ParseSubBody()
{
Match(new Token(TokenType.Symbol, "{"));
ParseLocalVarDecls();
switch (_currentSub.Kind)
{
case SubroutineKind.Constructor:
_codeGenerator.ConstructorDeclaration(_currentSub);
break;
case SubroutineKind.Function:
_codeGenerator.FunctionDeclaration(_currentSub);
break;
case SubroutineKind.Method:
_codeGenerator.MethodDeclaration(_currentSub);
break;
default:
ThrowCompilationException(...);
break;
}
ParseStatements();
//Make sure the method ends with 'return'. If the
//method is void, return an an arbitrary value. This
//could be left to the CG's discretion as well.
if (!_wasLastStatementReturn)
{
if (_currentSub.ReturnType == "void")
{
_codeGenerator.IntConst(0);
_codeGenerator.Return();
}
else
{
ThrowCompilationException(...);
}
}
_wasLastStatementReturn = false;
_codeGenerator.EndSubroutine();
Match(new Token(TokenType.Symbol, "}"));
}
private void ParseLocalVarDecls()
{
while (IsNextTokenLocalVarDecl())
{
ParseLocalVarDecl();
}
}
private void ParseLocalVarDecl()
{
Contract.Requires(IsNextTokenLocalVarDecl());
Match(new Token(TokenType.Keyword, "var"));
Token varType = NextToken();
while (true)
{
Token varName = NextToken();
Symbol variable = new Symbol(
varType.Value, varName.Value,
SymbolKind.Local, _currentClassName);
//Locals can't clash with parameter names.
if (_methodSymTable.HasSymbol(variable.Name))
{
ThrowCompilationException(...);
}
_methodSymTable.AddSymbol(variable);
_currentSub.Locals.Add(variable);
if (LookAheadToken.Value != ",")
{
break;
}
Match(new Token(TokenType.Symbol, ","));
}
Match(new Token(TokenType.Symbol, ";"));
}
private void ParseStatements()
{
while (LookAheadToken.Value != "}")
{
ParseStatement();
}
}
private void ParseStatement()
{
_wasLastStatementReturn = false;
Token keyword = LookAheadToken;
if (keyword.Type != TokenType.Keyword)
{
ThrowCompilationException(...);
}
switch (keyword.Value)
{
case "let":
ParseLetStatement();
break;
case "if":
ParseIfStatement();
break;
case "while":
ParseWhileStatement();
break;
case "do":
ParseDoStatement();
break;
case "return":
ParseReturnStatement();
break;
default:
ThrowCompilationException(...);
break;
}
}
private void ParseReturnStatement()
{
Match(new Token(TokenType.Keyword, "return"));
if (LookAheadToken.Value != ";")
{
if (_currentSub.ReturnType == "void")
{
ThrowCompilationException(...);
}
//Constructors may only return 'this'.
if (_currentSub.Kind == SubroutineKind.Constructor &&
LookAheadToken.Value != "this")
{
ThrowCompilationException(...);
}
ParseBLOCKED EXPRESSION;
}
else
{
if (_currentSub.ReturnType != "void")
{
ThrowCompilationException(...);
}
//As a convention, void methods return 0.
_codeGenerator.IntConst(0);
}
_codeGenerator.Return();
Match(new Token(TokenType.Symbol, ";"));
_wasLastStatementReturn = true;
}
private void ParseDoStatement()
{
Match(new Token(TokenType.Keyword, "do"));
ParseSubCall();
Match(new Token(TokenType.Symbol, ";"));
_codeGenerator.DiscardReturnValueFromLastCall();
}
private void ParseWhileStatement()
{
Match(new Token(TokenType.Keyword, "while"));
Match(new Token(TokenType.Symbol, "("));
_codeGenerator.BeginWhile();
ParseBLOCKED EXPRESSION;
_codeGenerator.WhileCondition();
Match(new Token(TokenType.Symbol, ")"));
Match(new Token(TokenType.Symbol, "{"));
ParseStatements();
Match(new Token(TokenType.Symbol, "}"));
_codeGenerator.EndWhile();
}
private void ParseIfStatement()
{
Match(new Token(TokenType.Keyword, "if"));
Match(new Token(TokenType.Symbol, "("));
ParseBLOCKED EXPRESSION;
_codeGenerator.BeginIf();
Match(new Token(TokenType.Symbol, ")"));
Match(new Token(TokenType.Symbol, "{"));
ParseStatements();
Match(new Token(TokenType.Symbol, "}"));
_codeGenerator.PossibleElse();
if (LookAheadToken.Value == "else")
{
Match(new Token(TokenType.Keyword, "else"));
Match(new Token(TokenType.Symbol, "{"));
ParseStatements();
Match(new Token(TokenType.Symbol, "}"));
}
_codeGenerator.EndIf();
}
private Symbol GetClosestSymbol(string symName)
{
if (_methodSymTable.HasSymbol(symName))
return _methodSymTable.GetSymbol(symName);
if (_classSymTable.HasSymbol(symName))
return _classSymTable.GetSymbol(symName);
return null;
}
private void ParseLetStatement()
{
Match(new Token(TokenType.Keyword, "let"));
Token varName = NextToken();
if (GetClosestSymbol(varName.Value) == null)
{
ThrowCompilationException(...);
}
if (!_methodSymTable.HasSymbol(varName.Value))
{
Symbol variable =
_classSymTable.GetSymbol(varName.Value);
if (variable.Kind == SymbolKind.Field &&
_currentSub.Kind != SubroutineKind.Constructor &&
_currentSub.Kind != SubroutineKind.Method)
{
ThrowCompilationException(...);
}
}
bool withArrayIndex = false;
if (LookAheadToken.Value == "[")
{
VerifyArrayAccessAllowed(varName);
withArrayIndex = true;
Match(new Token(TokenType.Symbol, "["));
ParseBLOCKED EXPRESSION;
Match(new Token(TokenType.Symbol, "]"));
}
Match(new Token(TokenType.Symbol, "="));
ParseBLOCKED EXPRESSION;
_codeGenerator.Assignment(varName, withArrayIndex);
Match(new Token(TokenType.Symbol, ";"));
}
There’s a lot of code here, but it really writes itself. Now we have a fully functional parser that delegates to the code generator the actual … code generation. Up next, generating fully functional C code by implementing a code generator for this parser.
NOTE: If you’re only interested in getting to a working version of a compiler, feel free to wait for the next post. Otherwise, I’m assuming you’re ready for some theoretical discussion.
One area where our compiler enjoys a huge relaxation is error handling and recovery. So far, we have taken the approach of failing whenever something looked wrong—the liberal sprinkling of “ThrowCompilationException(…)” in the code is unmistakable evidence that we’re not actually doing any recovery.
Compare this behavior to that of a C# or C++ compiler. For example, the following clearly invalid program produces three compilation errors, not just one:
C:\temp>type invalid_program.cs
class Program {
static int Main() {
i = 5;
foo();
return "hello";
}
}
C:\temp>csc invalid_program.cs
Microsoft (R) Visual C# 2010 Compiler version 4.0.30319.1
Copyright (C) Microsoft Corporation. All rights reserved.
invalid_program.cs(3,3): error CS0103: The name 'i' does not exist in the current context
invalid_program.cs(3,3): error CS0103: The name 'foo' does not exist in the current context
invalid_program.cs(3,10): error CS0029: Cannot implicitly convert type 'string' to 'int'
How can we introduce a similar behavior into our compiler? The Dragon Book [section 4.1.4] suggests four possible methods of error recovery:
- Panic-mode recovery—upon discovering an error, the parser should start discarding input symbols until it reaches a synchronizing token, such as ; or }. This is a fairly simple approach; in our example above, a compiler employing panic-mode recovery with ; as a synchronizing token will find all three errors in the program.
- Phrase-level recovery—upon discovering an error, the parser should perform error correction on the input.
- Error productions—modify the grammar to accommodate for common errors and issue appropriate error messages when the error is detected. Parsing can continue after the erroneous sentence has been processed, as there has been no error in the lexical sense.
- Global correction—upon discovering an error, find the minimal sequence of corrections to the source program. Although there are general-purpose algorithms that do this, in practice this approach is too costly to incorporate into any real-world compiler.
Of these four approaches, it would make sense to implement panic-mode recovery in the Jack compiler. The synchronizing tokens would be the semicolon, a closing curly brace, and the entire set of statement-beginning keywords (do, let, et al.). The implementation, however, is left as an exercise to the reader, or at the very least—to a much later phase of our compiler development.
The TechEd is finally over. Three days of fun in sunny Eilat with 67 colleagues from Sela and lots of good friends from the industry are done.
Thanks a lot for coming to my session—Deep Dive into Performance and Debugging in Visual Studio 2010! I’m not sure when the conference website is going to have the slide decks and demo code, and I promised you a blog post full of resources and links, so here it goes.
The slides and demos can be downloaded from here. It might take a little while to figure out the IntelliTrace and Profiler Guidance extensions, so feel free to shoot me an email (through the contact form) if you need help. [Besides, I’m planning a series of posts on these topics, so I might just answer your questions here on the blog.]
Here are some resources I used when doing the research for the session. They are not terribly organized, but reading them all will put you in the same frame of mind.
- Visual Studio Profiler
- SOS and beyond
- IntelliTrace
I hope you too found the TechEd an enjoyable experience. See you in 2012?