Compiler Class

As a Computer Science major at Michigan State University, I took the required "compiler sequence" of classes: CPS 451, 452, and 453. In this course sequence, students wrote a compiler for a programming language.

The courses differed from compiler courses offered by most Computer Science departments today in that:

• The sequence lasted an entire academic year. (MSU was on the quarter system at the time; under the semester system, this would have been two classes.)
• Students worked in pairs to write their compilers. Thus it was the first experience for most students in working closely with another programmer on a large project.
• The compiler was written from scratch - no lex and yacc. However, the instructor had written a utility that did some processing of the BNF grammar, thus providing some of the functionality of yacc.
• The compiler was to be written in FORTRAN-66. The answer to the question "Is FORTRAN-66 an ideal language in which to write a compiler?" is "No."

I am impressed that students these days write a compiler by themselves in one semester, albeit with more sophisticated tools than we had.

Code generation routine - with source code control line IDs

The compiler sequence - which has since been paired down to a single course - was somewhat controversial in the department, as some thought that too many course hours were being spent on a skill that wasn't going to be relevant to many students. Others, like me, thought it was a wonderful opportunity to work on a large project, particularly since it also provided experience working on a team.

Students paired off by themselves. This was arguably an unfair situation, because you wanted a good "compiler partner", and students who had already developed a good reputation were more likely to be able to get a good compiler partner. Thus the rich got richer, etc.

Bobb

In my case, choosing a compiler partner was simple. "Bobb" and I had been hired by the Computer Laboratory (academic computer center) on the same day, and had desks right near each other. I knew Bobb as a decent and intelligent fellow, and he thought the same of me, so the choice was a no-brainer.

MRR 3 years later (sorry, no pics from that year)

Bobb was a Jerry Garcia look-alike, and my hair was getting pretty long by then, too, though I lacked the beard. I'm sure we made quite an impression, especially since we were a couple of those "damned Computer Center people".

At the time, there was an antipathy between the Computer Science Department, which taught courses and did research, and the Computer Laboratory, which ran the campus mainframe, including developing the operating system for the machine. Computer Lab people thought Computer Science people had their heads in the clouds, and Computer Science folks thought the Computer Labbers had their noses in the mud. Those who straddled the two worlds, like Bobb and me, tended to identify with our jobs at the Computer Lab.

MNF

CPS 45x had the usual lectures, tests, and homework, but the main point of the course was writing a working compiler. We were supposed to write the compiler in FORTRAN, the most popular language at Michigan State due to the scientific bent of our mainframe's vendor, Control Data Corporation. Both Bobb and I considered ourselves grizzled veterans of that programming languages (even though I was only 19 years old at the time), and FORTRAN no longer held much charm for either of us. We therefore asked permission to use a different language, to make the course more interesting. The obvious choice was Pascal. The first Pascal compiler was written for CDC mainframes, and we knew it was reliable because our colleagues Kevin and Martha had written a word processor using that compiler, and I was maintaining that word processor with no trouble.

Unfortunately, a compiler team in a previous year had tried to write their assignment in Pascal and had failed. They had blamed the Pascal compiler. No one in the CPS department had had any practical experience with the compiler, so the instructor was in the uncomfortable position of not knowing whether to believe the students. He didn't want to repeat the experience, so he denied our request. This was frustrating to Bobb and me, and also ironic, since the language we were implementing was a variation of Pascal. So, we decided we'd have a little fun and use a non-standard FORTRAN compiler.

Though nearly all of our mainframe's users used FTN, the vendor's standard optimizing FORTRAN compiler, the system actually had four FORTRAN compilers installed:

• FTN, the currently-shipping optimizing compiler, with a few language enhancements.
• RUN, the vendor's older FORTRAN compiler, long since fallen into disuse. The older compiler was kept around in case anyone was still using assembly language routines that used the older calling sequnce. Interestingly, the older compiler - though it lacked a modern optimizer - had a more efficient register-based parameter-passing convention.
• RUNT, a very clever reimplementation of RUN by a team at University of Washington. RUNT was amazingly small and fast. However, it seems that I was the only one at our site who ever used it.
• MNF, the University of Minnesota FORTRAN compiler. This compiler was designed for instructional use: quick compilation times, no optimization, and good compile-time diagnostics. It implemented a few language extensions, and was the new kid in town, having been installed on our system only recently.

We chose MNF because:

• The quicker compile times would save us a little money. Each team was allocated a modest amount of computer dollars per academic term. These computer dollars translated to real dollars that the Computer Science Department had to pay the Computer Laboratory, likely part of the basis of the rancor between the two. Student were strongly urged to spend as few computer dollars as possible.  Bobb and I used a source code control system - very unusual for students - which helped deplete our dollar balance, making economy even more important.
• The better diagnostics meant you had a shot at eliminating the syntax errors in your program in fewer compilations. This was important because for most classes, students had a limit of 3 "runs" per day. That's right: you could compile (and if the program compiled, run) your program a maximum of three times per day. Batch mode only, with punched cards, of course.  I'm not absolutely certain that this limit applied to CPS 45x, but with the slow turnaround time on our aging mainframe, it wouldn't have made too much of a difference if the limit had been higher.  At any rate, records show that at the end of the last course in the sequence, our joint account had accumulated 272 runs.
• We thought we'd have fun with a new toy. Yes, playing with a new compiler was Bobb's and my idea of fun.

Midway through the year, Bobb and I had reason to regret our choice. Our parser just wasn't working right with a certain language construct. I desk-checked our code numerous times (you desk-check code a lot when you have only 3 runs / day), and just didn't see the error. Even though it seemed silly, I began to suspect a FORTRAN compiler error. I inserted a no-op line of code like:

      IF(.FALSE.) GO TO 100

into the offending basic block to nullify whatever code-generator cleverness was the culprit, and that fixed it!

We filed an MNF bug report with the University of Minnesota, but I can't recall what became of it. I'm pretty sure we never told our very good instructor Hal the wages of our sin of experimenting with a new compiler on a serious project.

Generated assembly code, with tuples as comments

R

One of the students in the class was the very intelligent R, who was also one of the most beautiful women I ever met. Compiler class was not the place I expected to meet such a woman.

After a few weeks, I started to flatter myself that R and I were the smartest kids in the class.  Meanwhile, many of us male students became envious of Dennis, R's compiler partner. Once, after I answered a question in class, Bobb razzed Dennis: "My compiler partner is smarter than yours." Dennis replied: "Maybe, but mine is better looking."

I was smitten. However, I could rarely think of anything to say to R, especially if it required stringing together more than two syllables. One day, though, my chance came to me unexpectedly. R actually approached me and, mistakenly believing I had already taken the CPS 42x sequence of classes, asked me to help her with a particularly tough logic circuit concept. Fighting to keep my blood pressure under control, I had to admit that I hadn't taken the classes yet - but I was willing to look at the problem anyway. If I recall correctly, R figured out the answer herself while explaining the question to me. So, I guess that counts as a win. But, alas, there were no more homework help sessions.

Peer code review was virtually unheard of in the CPS department at the time, but somehow there was a one-time code review session in the course, in which I got to see code R had written. It was unbelievably complex, the very embodiment of spaghetti code. I was unsure as to whether to be impressed that she could get code like that to work, or to be horrified at her violation of all civilized coding standards. Given my crush on her, I leaned toward the former.

Science Fair

That year, my father was the director of the Metropolitan Detroit Science and Engineering Fair. That in itself was a sign that dogs and cats were soon going to be living together, as my father was a construction guy, not a scientist. But he was recruited because he had a reputation for getting things done.

Dad had come into the science fair world based in my participation in science fairs in high school. My chemistry teacher, Leo J. Klostermann, was supposedly the leading high school science fair teacher in the country, and as a result, science fairs were a big deal at my school. (Note to high school students reading this: doing a science project on cryptography will win you all of the special military awards, even if your project isn't really as good as the other guys'.)

The top performers at a regional fair like Detroit's got to compete at the International Science and Engineering Fair in Denver. One of the many responsibilities of a science fair director was to arrange transportation of the top projects to Denver. Though my father was a mid-level manager at Ford Motor, and in fact worked in the shiny World Headquarters in Dearborn, MI, he was a construction project coordinator, and didn't work on the car side of the house. Perhaps for that reason, or perhaps because Ford didn't have any spare trucks, Dad was unable to scare up a sufficiently large vehicle for the task in-house.

Fortunately, my father found a guy at General Motors who had access to a one-of-a-kind prototype truck that had just been released from testing. This unnamed vehicle was about as large as a decent-sized delivery van. It was painted an ugly green, and due to its prototype status, parts of its interior were made of plywood. I will give them credit for at least painting the plywood.

My father needed drivers to get the truck from Detroit to Denver, and for that, he looked to me and my 16-year-old brother Tom. School was in session, so we didn't want to dally. The plan was for Tom and me to take turns driving. Using the back of the largest science fair project, we created a space in the cargo area behind the driver's seat big enough to hold a cot, for use by the son not driving. My loquacious 14-year-old brother Bill was sent along, possibly to help keep the driver awake. Or possibly my parents were trying to reenact the Sullivan brothers.

The truck had a blind spot.  Tom figured out a way of dealing with it:  he'd slow down, and then rapidly accelerate (to the extent possible in that truck) while looking out the side mirror.  Assuming there wasn't a vehicle behind us matching our acceleration, he'd be able to see whether there was anyone back there.

I didn't have a commercial driver's license, and of course neither did my 16-year-old brother. I'm not sure why this never came up. Fortunately, though, Tom and I had learned to drive a stick shift on my mother's famously kvetchy Mustang, so we were more than ready for the truck's transmission. That is, until we reached Colorado, when the truck started getting really tough to shift. We stopped and called my father, who told us about "double clutching". That allowed us to limp to Denver, where we took the truck to a repair shop. The mechanic's jaw dropped when he saw the one-of-a-kind vehicle. Fortunately, he was able to fix it.

As an incredible coincidence, one of the 12 science fair projects in the truck belonged to R's brother E. R and I lived quite some distance apart, but the Detroit fair covered a wide geographical area. Given R's very common last name, I'm not sure how I suspected that E was R's brother. But I confirmed it with R one day in class, in a gloriously multisyllabic conversation.

Somehow I got it into my head that becoming pals with E in Denver would help me get to know R. However, E was not a particularly pally guy (I probably wasn't either), and this idea came to nought.

Despite the two drivers, the trip to Denver took the better part of a week. Though Bobb was understanding about having to shoulder the burden himself during that period, I was concerned about not doing my part for the term project. Fortunately, there was a separate but related assignment that involved implementing a certain non-trivial algorithm in the language processed by our compiler. We had to not only code the algorithm correctly, but also compile and run it with our own compiler and show that it produced the correct results.

I coded the algorithm on the road and mailed the paper copy to Bobb. (This was before widespread access to email.) He received it before my return, but discovered that the program gave the wrong answer. It turned out that I had made a couple of errors in coding it and hadn't adequately desk-checked it; the compiler itself was correct. Bobb was able to fix the bugs, but the experience gave me a crumby feeling. Nowadays I'd say that the ordeal was due to violating the principle of testing only one thing at a time.

The Language

The language we implemented was a bastardized version of Pascal. When the course had originally been taught, the language was in fact a proper subset of Pascal. However, in subsequent years, to discourage cheating, the language had been tweaked so that each year it was significantly different than what it had been like in all previous years. (Years later, I worked with an MSU Computer Science instructor who pioneered automated checking of cheating on Computer Science assignments. I'm not sure that I like what this says about Michigan State U.)

By the time I took the class, the mutated language's syntax was bizarre and displeasing. This made it all the more amusing to hear, at the end of the course, that one of the students was planning to market his compiler commercially. Not only was the language awful, but our compilers all ran quite slowly compared with commercial compilers. The student was concerned about intellectual property rights, thinking that perhaps the University would feel it owned the compiler he wrote for class.  I guess he was ahead of his time in even considering this possibility.  But he defiantly told the instructor that he was going ahead anyway, and wasn't planning on sharing his profits with the University. The instructor smiled and said he didn't think there would be a problem.

Epilog

Bobb and I did well in the class.

R got married - to a guy in Colorado, I heard - shortly after the end of the last course in the sequence. Sigh.

I went on to use compiler technology in a couple of projects years later:

• In 1996, I developed a PHP-like language for a mainframe web-enabling product, IntraGate.  I wrote its processor using flex and bison.  But there was no machine code generation; it just interpreted the generated tuples. 
• In 2009, I developed a programmable task processor for a file transfer product named MOVEit Central.  The source language, which was meant to be generated by the GUI front-end, used XML syntax.  I accidentally wrote its parser while playing around with the Microsoft XML DOM API one night.

I still dream of writing a compiler for a real language, perhaps the surprisingly obscure CYBIL (19MB PDF), which I once thought was really cool.