Elements of Computing Systems Chapter 11c

Exercises

We began the meeting by recapping where we left off last time—outputting VM code from our new CompilationEngine—and discussing how we should proceed. We were stuck trying to output code for the following Jack expression:

do Output.printInt(1 + (2 * 3));

Which should result in the following VM code:

push constant 1
push constant 2
push constant 3
call Math.multiply 2
add
call Output.printInt 1

Until now, we had been outputting VM code for each token but now we had to build up some sort of parse tree so that we could approximate the reverse Polish notation of the VM code.

We debated whether to build a parse tree data structure and then use that to emit VM code or to modify our existing CompilationEngine to emit VM code but use the Ruby call stack itself as the parse tree. As it initially seemed that creating a parse tree would be the more valuable learning exercise of the two options, we proceeded to extract a new ExpressionParser class so that we could test this in isolation.

We began by attempting to parse expressions containing only numbers, e.g. 1, by creating separate classes, all with an emit method that orchestrate our existing VMWriter to produce the correct VM code:

• Add Expression Parser that parses numbers

With that base case done, we now passed the SymbolTable to emit to handle variables such as a:

• Parse variables

Following the codeWrite(exp) pseudocode from the book, we implemented binary expressions such as 1 + 2 by doing the following:

1. Emit the left-hand expression;
2. Emit the right-hand expression;
3. Emit the operation.

• Parse binary expressions

Then to check the binary expression handling could work with nested expressions, we added support for parentheses so we could parse things like 1 + (2 + 3):

• Parse expressions with parentheses

Then unary operations such as ~a and -5:

• Parse unary operations

Keywords such as true and false (but ignoring this for the time being):

• Parse basic keywords

Deal with the special arithmetic case of multiplication which is handled by a function call:

• Parse multiplications

At this point, we had run out of time and quite a few members of the group were frustrated by our approach and lack of progress. In choosing to build up a parse tree using a new ExpressionParser, we ended up re-implementing a lot of the code in the existing CompilationEngine. Another warning sign being that we—once again—struggled with advancing the tokenizer at the appropriate time.

Having spent three meetings on this chapter, we discussed whether there was any value in continuing, particularly if it was jading attendees. We agreed that it had been useful to at least start emitting VM code but that we were strangely lead astray by the previous chapter's exercise to first produce an intermediate XML format for our Jack programs.

We had hoped that this would lead naturally into our current exercises (as previous chapters had done) but it seems to have needlessly duplicated effort. We wondered whether our use of Builder had made us couple XML generation too tightly with our parser and whether we weren't following the book's authors' original intentions with this chapter.

Though there was some dismay at abandoning the exercise, we agreed to push onto Chapter 12 in our next meeting but encouraged others to forge ahead in their own time. There was talk again of implementing a Jack parser using tooling such as Parslet or Treetop or even transforming our XML output into VM code.

Asides

• When first implementing the Number class, we tried using a Struct with no values but this raises an ArgumentError. Tom mentioned that he'd hit this problem in his book but that someone had written to tell him that it is possible to create "nullary" Structs by passing nil instead:

Struct.new
# ArgumentError: wrong number of arguments (0 for 1+)
Struct.new(nil)
#=> #<Class:0xdecafbad>

• James dazzled us with Ruby's flip-flop operator:

1.upto(10).each do |i|
  puts i if (i == 2) .. (i == 6)
end
# 2
# 3
# 4
# 5
# 6

Some of us were particularly intrigued by how this worked (e.g. how often are the predicates evaluated) so we tried this:

def flip
  puts "flip?"
  3
end

def flop
  puts "flop?"
  6
end

1.upto(5).each { |i| puts i if (i == flip) .. (i == flop) }
# flip?
# flip?
# flip?
# flop?
# 3
# flop?
# 4
# flop?
# 5

This showed us how Ruby must be keeping track of the truthiness of the first predicate in some hidden internal state until the second predicate becomes true.

Apparently there is a proposal to remove this from the language but Kevin dug out someone legitimately using it.

Thanks

Thanks once again to Leo and Geckoboard for hosting and providing much needed sustenance during the meetings.