Midterm 2 key available

I've graded today's midterm and posted a key.

Overall you did well.  Maybe it was a bit too easy, but I'm satisfied that it showed you had a grasp of the material.  I don't think judging finer gradations of how deeply you understand one topic or another was something I could reasonably expect from a one-hour exam that covered so much material.

One more example question ...

I haven't thought of exactly how I would write this up ... but I can imagine asking you to create a data flow analysis for some particular problem, such as the "variables must be initialized on all paths before any possible use" check in Java.   I might give you one set of data flow equations as an example, and ask you to modify them (and describe what the gen and kill sets would be) for a different problem.

Sample final exam questions - part 2

These aren't from old final exams, but are sorts of things I could ask in the midterm Friday.

For these, assume a computer with a load/store architecture (that is, operands of any instruction other than load or store must be a register), and the following instructions  (rX are registers, mem are memory addresses, ";" introduces a comment till the end of the line
ADD  r0, r1, r2   ;; r0 := r1 + r2
SUB  r0, r1, r2   ;; r0 := r1 - r2
BZ   label    ;;  Branch if result of last operation was zero
BN  label     ;; Branch if result of last operation was negative
BNZ label   ;; Branch if result of last operation was not negative
LD  r0,mem  ;; r0 := Memory[mem]
ST  r0,mem  :: Memory[mem] := r

Assume an unlimited set of registers (i.e., assume that register allocation will be a separate step after generating code).

1a. Show an AST and then assembly code for  the following   (which might be Java or C or some similar language).

x = x + y;
y = y - x;

1b.  If your answer is not already in register SSA form (SSA except for memory references), show the assembly code in register SSA form.

2.  Show an AST and then assembly code for the following.

while (x < 0 || x < y) {
   x = x + y;
}

Sample final exam questions

We can discuss these in class on Wednesday, but you might want to try to work them out yourself in advance.

The first two are from a take-home exam.  Questions for take-home exams are written with the assumption that people can use search engines and compiler tools, and without quite the time constraint of an in-class exam.

---

1. Suppose class B extends (is a subclass of) class A, and we have a method M with the following Java signature:
B M(B o)
or, in Cool syntax
M(B o): B

The Java and Cool type systems do not allow passing an A object to M, but they do allow assigning the return value of M to a variable of type A. Why?

Be brief but clear and concrete. Don't tell me it is because it would be a violation of the type rules; I want to know why those type rules are in Java and Cool.

---

2. Storage for a Java variable of type int is allocated in the stack (activation record), as is storage for other primitive values like booleans. However, while references to objects are stored in the stack, storage for the objects themselves (including for example Int objects) is allocated in the heap. Why the difference? Be clear, precise, and brief.

---

The next question makes more sense if you are familiar with stack architectures and stack-oriented virtual machines (e.g., JVM), which we did not talk about this term. Nonetheless you may be able to figure it out.

---

3. Some of you generated code for the stack-oriented Java virtual machine, and some of you generated code for a physical processor with registers. If you generated Java byte code, you had to calculate the maximum number of stack slots required for expression evaluation. It is relatively simple to translate stack-oriented code into register-oriented code, provided you have as many available registers as the maximum required stack depth. Briefly describe how, and illustrate with an example of translation from postfix or stack-oriented code to register  oriented code for the expression

a + b − (c + d).

---

I'll try to make up a few new questions before Wednesday, since my stash of (suitable) old questions seems pretty small.  Ideally I would like to cover type checking, code generation, data flow analysis, and register allocation.  Realistically, in a 50-minute exam, I will not be able to cover everything, and it will difficult to craft questions that require some real understanding and yet can be answered quickly.  Probably there will be less of the "explain why" kind of question and more of the "generate code for this" kind of question, though there may be some of each.

Terminology: "Forward" and "Backward" analyses

I got to thinking about terminology after today's lecture, and I think I see how terminology for "forward" and "backward" analysis can be confusing.  When we "look forward" to see what will happen further ahead in execution, that's actually a "backward" flow analysis ... because the information flows backward (we are looking forward, but bringing the information back to here).  It also indicates the way an iterative data flow analysis algorithm orders the nodes it visits.  In a backward flow analysis, it is most efficient to iterate from last to first, again because that's the direction the information is moving.  In a work-list algorithm, if values at node N change, it is the predecessors of N that need to be added to the work list.

Bottom line: the term comes from which way the information is moving, which is reverse of the direction we are looking for it.  So if a flow equation takes in information from the successors of a node, it is a backward analysis, and if it takes in information from the predecessors of a node, it is a forward analysis. 

Reminder - LALR(1) quiz tomorrow (Friday)

Remember, tomorrow (26 Feb) I will give a quiz (short midterm) so you can show that you've mastered the LR(0) and LALR(1) parsing material that gave you trouble on the first midterm. 

Object code lecture notes

Here are my lecture slides on LLVM IR code generation (up to data flow analysis, which I posted yesterday).  Some of these have been posted before, but I think the first of those below, on walking the AST to generate LLVM IR, has not.

• From AST to IR  (expressions, control flow, short-circuit conditions)
• Addressing in LLVM, Where things live and More on LLVM addressing of objects 

I think that's it, but if you're missing something you recall from lecture, please let me know.

Data flow analysis intro slides

Here are the slides I used today, with a couple of corrections to the mistakes you caught.  (There might be more mistakes ... please let me know if you spot one.)

Clang and C++

I experimented a bit with how Clang compiles C++, but I'm not sure it provides much guidance.   With the classes:

class Rect {  ... };
class Square : public Rect { ... };

I end up with the llvm type declarations:

%class.Rect = type { i32, i32, i32, i32 }
%class.Square = type { [16 x i8] }

It does use bitcast to call inherited methods:

 %0 = bitcast %class.Square* %s to %class.Rect*  ; <%class.Rect*> [#uses=1]
  call void @_ZN4Rect9setBoundsEiiii(%class.Rect* %0, i32 0, i32 0, i32 10, i32 10)
  %call = call i32 @_ZN6Square4areaEv(%class.Square* %s) ; [#uses=1]

The strange names like "_ZN4Rect9setBoundsEiiii" are from "name mangling" in C++, which is how C++ provides overloading while maintaining compatibility with C which does not.  The source code name is "setBounds", and the random junk is added to make it unique. 

My C++ mojo has not been sufficient so far to really figure out how the dynamic dispatch is working, but it at least appears that the Clang front end (which is not as complete as the gcc front end) is using casts instead of using nested structures.  That doesn't mean nested structures is a bad idea ... I think either way should work.

Lecture notes for Friday (more fun with addresses)

Tomorrow's slides (Friday 19 Feb) are here

It's pretty much a continuation of Wednesday's look at how we address things in LLVM, starting with a repeat of the last slide of LLVM code from Wednesday.  Normally I try not to stuff quite so much onto each slide, but in this case I really wanted stuff side-by-side, so we can compare between C and LLVM code.  There is also a slide that shows how the LLVM code becomes assembly code (with x86 assembly; of course it will look a little different if you produce assembly code for a different machine architecture).

LLVM web interface

Try the online LLVM demo to compile bits of C code into LLVM intermediate representation.   Also you can meet Bitter Melon, one of the smartest cats I have been introduced to.  Most cats are not very good programmers, because they are too easily distracted.

Thanks Kristy for the tip.

LLVM addressing slides

My slides for today's lecture (Wednesday 17 Feb) are full of example code ... it might be useful to have a printed copy, or an online copy to refer to.  A PDF version is  here.

llvm travails

I am now zero for three on compiles of llvm + Clang on ix.  It seems that the nearness to a new release is indeed causing difficulties ... every time I do "svn update" I get several newly updated files.  The first compile took 3+ hours; subsequent compiles have been a little faster.   I'll give it a couple more tries before I admit defeat and either pull an older version from SVN or try put together a binary-only set.

Grammar booboo

Suzanne asked about a weird production in the starter grammar I provided ... which seems to allow an expression on the left-hand-side of an assignment.    Oops. 

In many programming languages, there are "lexprs" (left-hand expressions) and "rexprs" (right-hand expressions), and there can be lexprs inside rexprs and vice versa.  For example, you could have something like this in Java:
     myArray[ j + 5 ].itsField =  (foo.bar()).baz();
where j + 5 is an rexpr (denoting a value), but myArray[j + 5] is a lexpr  (denoting a location from which we can get a value or into which we can store a value). 

But not in Cool.   All fields are private.  There are no arrays.  I don't think you can have anything more complicated than a simple identifier on the left side of an assignment.

My bad.  You could just check for this in the type-checker, but a better solution is to fix the grammar so that the left side of an assignment is an identifier and not an expression.  Good catch Suzanne.

A small request: README files

I get many assignments turned in as archives that expand to "Cool" or "Compilers".  I look in the README.txt file to remind me of which assignment was turned in by whom ... and usually what I see is the original README.txt from the scanner assignment.  Please replace the contents of the README file with some identifying information (e.g., "This is the type checker assignment, turned in by I.M. Smart and U.B.A. Mazed").   Thanks.

(I can deal with what I've got so far ... but please start doing this for the type checker and code generator assignments.)

List of static semantic checks

Thanks Alex for sifting through the Cool manual and making a list of all the static semantic checks that the "type checker" is supposed to check.  (The scare quotes are because, strictly speaking, a lot of these are not type rules, so really this is a static semantic analyzer which includes type checking and other checks).

1. [No undefined classes, pg. 7] If class C inherits B, then B must be
defined somewhere. This goes for any type specified by the programmer (ex:
let x:Foo := new Foo in 5, where Foo is never defined).

2. [No cycles in the class hierarchy, pg. 7] Class C must not inherit C,
nor should it inherit any other class that eventually inherits C.

3. [No class redefinitions, pg. 5] No two class definitions should use the
same name, i.e. "class C { ... }; ... class C { ... };" is invalid.

4. [No stdlib redefinitions, pg. 18] No class definition may use the names
Object, IO, Int, String, or Bool.

5. [Limited stdlib inheritance, pg. 18] No classes may inherit from Int,
Bool, or String. Classes may inherit from Object and IO.

6. [No attribute/method redefinitions, pg. 5] In the same class, no two
attributes/methods can have the same identifier. A method and an attribute
may share the same name, but not two methods or two attributes.

7. [No inherited attribute redefinitions, pg. 7] If class C inherits B,
and B defines an attribute "foo:Int", C must not contain an attribute
called foo.

8. [Limited inherited method redefinitions, pg. 10] If class C inherits B,
and B defins a method "foo(a:Int, b:Int):Int {}", then C can only
change the , it must not redefine the type signature of foo.

9. [No "self" redefinitions, pg. 12] It is an error to assign a value to
self, bind self in a let or case expression, or use self as the name of a
parameter to a method.

10. [Need a Main class / main method, pg. 19] Every program must have a
class called Main. In Main, there must be a method called main with no
parameters.

11. [All attributes/methods must typecheck, pg. 9] All methods and
attributes must pass the typechecker.

LALR(1) Howto draft

You asked for a brief, step-by-step guide for creating LALR(1) context-free state machines (CFSMs).  I have created a draft:  Constructing the LALR(1) CFSM

I was shooting for 2 pages or maybe 3, but ended up with 7 ... and that's with no pictures and no worked examples.  I am willing to work on this some more to make it better, but I could use some feedback on the current version.  Is this clearer than the books you are using?  Less clear?  Is it too verbose, or too concise?   Too formal or too hand-wavy?  Can you see how the inductive rules for First and Nullable are the underlying logic for the pseudocode in the books?

There are small discrepancies in the construction from book to book.  I think the Dragon Book mixes together the Nullable and First set algorithms, placing an epsilon in the first set to indicate that a terminal symbol is nullable, while Crafting a Compiler treats these as two different analyses (as I do in this guide).  There may also be bugs in my description.  If you find something confusing, or think you have spotted an error in my instructions, please let me know.

AST assignment due Monday

As we decided in class, the AST-building assignment will be due Monday.

The requirement is very simple:  Parse Cool programs, and print the tree in any way you like.   Dot (GraphViz) is one very nice way to look at trees, but if you use it I suggest you find a way to look at just parts of the overall AST, because graphic depictions of large trees get unreadable fast.  While a nice indented listing is also good, I wouldn't invest a huge amount of time building a tree pretty-printer unless you think you will have other uses for it later.

AST example: Itsy bitsy teeny weeny compiler

Here is a very very simple example of  building (and then using) an AST. 

tiny.cup parses a very simple language of assignment statements with expressions as right-hand sides.  It builds a simple AST,which is passed back to the driver.

The driver (Tiny.java) obtains the AST from the parser, and hands it off to an evaluator. The evaluator emits simple stack code (in the form of pseudocode ... but you can see how you could modify this to be either real code in a language like C or Java or instructions to a stack-machine interpreter).

Midterms are graded

... and will be handed back at the end of class on Monday.

Scores overall are pretty low, and what I learned from grading them is that we really aren't done with LR parsing  (LR(0) and especially LALR(1)) yet.  Some of you are close to mastering it, some are pretty lost, and many are somewhere in between. 

Why do I even care?  After all, we've got nice programs like bison and cup to do this for us.  But I do care, because LR parsing is an exemplar of a couple important algorithmic patterns:

• Treating a back-tracking problem (searching for a parse tree) as a non-deterministic search (sending angels out to scout different possible parses) and then, because the number of branches we need to explore is finite, folding them together into a deterministic algorithm (just like the subset construction from NFA to DFA).  This is a powerful pattern that has other applications. 
• Applying a set of rules (adding new items (productions) in a CFSM state) until none of the rules change anything.   We'll see this again in data flow analysis, and it appears in other domains as well.  Often we can look at a problem this way or in other ways, but this way is simpler and clearer.  For example, although most textbooks describe computation of "first" and "follow" sets in other ways, the simplest description is in terms of a set of recursive set inequalities that can be applied over and over until nothing changes. 

Could you grok this just as well without mastering the details of LALR(1) parse table construction?  Maybe ... but I think it helps.  As an analogy, consider that you studied and were expected to really understand red-black trees in data structures, even though there are perfectly good implementations of red-black trees available to you in libraries.    But red-black trees illustrate important concepts about maintaining balance within an acceptable bound and rebalancingwith local operations.  You'll forget the details, but the concepts stick partly because you mastered those details once. You'll forget the details of LALR(1) parsing approximately Wednesday of spring break (and so will I, and then relearn it once again next time I teach it), but the important concepts will stick better if you force yourself to really, really understand it inside and out for at least a little while.