The team presents its project and demos its compiler.
euclid: 335/45, 1260/210, 1078/546
primes and primes-sieve: 20, 100, 1000
horner: 1, 14, 2.6, -8
horner-modified: 1/-4/2/9 and same inputs; -3/2/2/1 and same inputs
lists-and-functions-tests: lots of embedded tests
errors: scan-errors and type-errors
sort-app: 1/2/3/4/5, 5/4/3/2/1, 1/8/4/5/6/3/7/2
You can download these programs as a .tar.gz file.
First, I'd like each person to debrief the compiler project, answering the following questions:
Your answers can refer to programming practices, languages, tools, project management, teamwork, course content, ....
This semester, I would like for you to give special thought to two decisions we made early: a team of size six, and designing your own language.
Be as specific as possible. I'd like to use your answers to improve the course next time around.
Second, I would like each person to comment on the contribution made by each member of the team:
We have talked about the analysis phase of a compiler: taking a program written in a source language as a stream of characters, doing lexical analysis to generate a stream of tokens, doing syntactic analysis to produce an abstract syntax tree, and doing semantic analysis to ensure that the AST satisfies the language definition. We have talked about the synthesis phase of the compiler, which converts a semantically-valid abstract syntax tree into an equivalent program in the target language: building a run-time system to support the execution of the target program, translating the AST through one or more intermediate representations such as three-address code, translating the final intermediate representation into code in the target language, and optimizing the code.
What a busy semester! And you wrote your own compiler. As much work as it turned out to be, I think you probably learned a lot from writing such a large and complex program. In fact, that is probably the only way that we can really learn how to program.
For all of the technical content of this course, writing a compiler is, at its core, a software development project. All of the issues that matter when we write any other large program matter when we write a compiler.
For example, software projects typically face the problem that the input/output specification changes over time. Compiler developers must deal with the volatility of the source language whenever the language is new or undergoing change. Even a mature language such as Java has undergone significant changes recently, with more on the way. The output specification may also change. Target machines evolve, and language users always seem to want the compiler to run on a new target machine or platform.
Software developers depend on the quality and support of the programming tools they use; the same is true for compiler writers. These tools include the programming language used to implement the compiler and support tools such as IDE, profiler, build management, scanner and parser generators, and the like.
Testing is an essential component of any software development project. How did you test your compiler? Did you have a suite of test programs that exercised all of the important features of your scanner, parser, semantic analyzer, and code generator? Did you have any way to run your tests automatically? [ More on JUnit, SchemeUnit and Ruby's Test::Unit... ]
Finally, project management has a huge effect on the implementation of any project as large as a compiler. This includes project planning as well as managing the work of a team of developers collaborating...
One way of exercising a compiler is to write the compiler in the source language being compiled. This serves to test the compiler, but more importantly, it makes it possible to port the compiler to a new target machine by writing only a new code generator and compiling it with the existing compiler. This creates a "chicken and egg" problem that we considered back in Session 2. Remember this?
What does this diagram show?
Quick Question: How close are your BigRig language and compiler to being good enough to write a BigRig compiler?
My favorite story about bootstrapping a compiler and implementing a language in itself isn't the Lisp story, which I told earlier in the semester -- though it is a classic story about a seminal moment in computing! My favorite story is the Squeak story.
Back in the mid-1990s, computing pioneer Alan Kay assembled his original team from Xerox PARC and went to work at Disney, to develop the next generation of digital media. They wanted a software development environment in which to build educational media for use by children and non-programmers. Their original Smalltalk could do the job, but none of the modern implementations provided the primitives and power they needed. They considered other modern languages, most notably Java, but found them to be too limiting. So they turned their attention back to Smalltalk and considered how to make a Smalltalk environment that would do what they wanted.
What they had to work with: an old implementation of Smalltalk-80 that ran on an old Mac. A Smalltalk implementation consists of a virtual machine, which interprets code in an intermediate representation, and an image, or the object memory that is the program.
What they wanted: a VM implemented in C, for maximal portability and speed, and an image implemented as much in Smalltalk as possible, for maximal control and flexibility.
What they did was something like the bootstrapping idea we saw above, with a new twist. They...
You can download Squeak from squeak.org, under the freest of free software licenses.
You can read the whole story, as well as some interesting technical ideas that go into the implementation of a pure object-oriented language, in the paper "Back to the Future", by Dan Ingalls and his colleagues at Squeak Central:
For what it's worth, if I needed a virtual machine and had all the money I needed to hire anyone I wanted, I'd ask Dan Ingalls. His work on Smalltalk in the last thirty years, creating many of the ideas that everyone takes for granted these days, is remarkable.