Teaching & Learning

An Incremental Approach to Compiler Construction

Abdulaziz Ghuloum (Indiana University), An Incremental Approach to Compiler Construction

Compilers are perceived to be magical artifacts, carefully crafted by the wizards, and unfathomable by the mere mortals. Books on compilers are better described as wizard-talk: written by and for a clique of all-knowing practitioners. Real-life compilers are too complex to serve as an educational tool. And the gap between real-life compilers and the educational toy compilers is too wide. The novice compiler writer stands puzzled facing an impenetrable barrier, “better write an interpreter instead.”


The goal of this paper is to break that barrier. We show that building a compiler can be as easy as building an interpreter.

This paper from the Scheme workshop presents an extended tutorial showing how to implement a compiler from Scheme to x86 assembly language. The compiler is written in Scheme, obviously (something that may confuse students, I might add, so beware).

An important aspect of the presentation of the material is that the compiler is built incrementally, and the product of each step is a working compiler for a growing subset of the language. This is similar to the EOPL approach. In contrast many compiler textbooks and courses follow a different route, in which each phase is dedicated to building a different part of the compiler (i.e., lexer, parser etc.), and thus the student only sees how the parts interconnect, and gets the satisfaction of seeing the compiler work, at the very end of the process.

Supporting material can be found here.

Computational Thinking

I know this is slightly off topic for LtU, but I see Philip Wadler is collecting material aimed at introducing students and the general public to the discipline of computation, a subject near and dear to my heart.

I will not elaborate my thoughts on this subject here, but I remind people interested in this topic to search the LtU archive (specifically the teaching and learning department) since items related to this goal have appeared here occasionally.

This is also a chance to mention again my suggestion that someone translate Doug Hofstadter's Scientific American columns introducing Scheme to a general audience into Haskell.

LASER Summerschool

As far as I know the LASER Summerschool has not been mentioned on LTU yet.

We have a fine lineup of speakers, including Miguel de Icaza(who gave a great presentation at the Lang .NET symposium), Andreas Zeller whose book on debugging is an instant classic, Mary Poppendieck whose presentations were the highlight of last year's JAOO, Ralf Back who as usual will ensure sound foundations, and of course Bertrand Meyer who needs no introduction!

Registration is open until August 31.

I hope to see many of you in person on Elba.

ACL2 in DrScheme

Via the plt-scheme mailing list:

We are pleased to announce the first public release [beta 7] of ACL2
in DrScheme, a combination of the ACL2 theorem prover system with the
DrScheme programming environment. The objective of this project is
to provide a development environment for ACL2 suitable for novice
users as well as enhancements of ACL2 that are attractive for the
typical undergraduate student (graphics, interactive games, sound).

There's a tutorial with screenshots and some examples on the ACL2 in DrScheme web page.

I'm always happy to see reasoning about programs introduced at the undergraduate level. I wonder what the LtU community would do with a tool like this. What cool things would you teach with a beginner's theorem prover?

Lisp is sin

People are discussing this blog post all over, so we might as well mention it here.

The discussion is quite balanced, though you are likely to disagree about the specifics. One issue, discussed here repeatedly, is that code=data doesn't require S-expressions. Lisp expressiveness runs deeper than that.

Our discussion of Spolsky's Java Schools essay is here, by the way.

Insights on teaching computer programming

I have been teaching programming for nearly ten years now, to university students from the first to the fourth year, to both CS majors and non-CS majors (all in technical fields). I have tried to distill results from programming language research into these courses (and wrote a book in the process, CTM). Recently, I had two insights:

1. The best year in which to teach a programming course based on programming concepts is the second year. In the first year, students are not mature enough. In the third and later years, students get conservative. In the second year, they have enough maturity to understand the concepts and enough openness to appreciate them. At UCL, we have been doing this for two years now for all engineering students (more than 300 in Fall 2005) using a first-year course based on Java, and it works remarkably well (better than I expected).

2. Students can be taught programming semantics in the second year. This can succeed if: (1) the semantics requires very little mathematical baggage, just sets and functions, (2) the semantics is factored so it can be taught incrementally, and (3) the semantics is simple and uncluttered so that students can work out a program's execution with paper and pencil. The semantics of CTM is one example that fits these conditions. The students consider the semantics the hardest part of the course. I think it's because they've never been exposed to this kind of formalism, so they are a bit unsettled by it. But I am convinced that students in any technical field should be taught programming language semantics at least once in their careers. It should be as basic as algebra or calculus.

What do you think? I would appreciate hearing your experience and comments. Here are the course notes of the latest version of my course (they are in French; there are English course notes too but they are not as nice for the second year).

The undergraduate language course: what to do?

Thinking about teaching our undergraduate PL next semester, I've been digging up lots of suddenly interesting readings. The teaching about PL project links to much information, and Wadler's and Felleisen et al.'s critiques of SICP were enlightening as well.

Most recently I stumbled upon Joseph Bergin's writings on teaching, in particular ""The undergraduate language course: what to do?" (SIGPLAN Notices 36(6):20-22, 2001), which describes a taxonomy of course approaches: "historical", "smorgasbord", "interpreter", and "principles". Also relevant is a recent article "In Computer Science, A Growing Gender Gap: Women Shunning a Field Once Seen as Welcoming" by Marcella Bombardieri (Boston Globe 2005-12-18).

(I'm sorry I couldn't find Wadler's and Bergin's articles freely available online.)

Monads in Ruby

Monads in Ruby, a several-part work in progress, is an attempt to explain and demonstrate monads in Ruby. It looks pretty good so far, although I feel like we could coax a friendlier syntax out of Ruby with a little effort. Maybe in Part 4!


Obligatory LtU connection: the author credits Dave Herman's Schemer's Introduction to Monads as an inspiration.

(One of my co-workers mentioned this to me. I think he might have been making fun of me...)

Felleisen: How to Design Class Hierarchies

My talk will instead present a novel approach to the first-year programming curriculum. Specifically, I will explain how a functional semester ideally prepares students for the true essence of object-oriented programming according to Alan Kay: the systematic construction of small modules of code and the construction of programs without assignment statements. Experience shows that these courses prepare students better for upper-level courses than a year of plain object-oriented programming. Initial reports from our students' co-op employers appear to confirm the experiences of our upper-level instructors. (full abstract)

We discussed this approach (FP as an introduction to OOP) before. This presentation is from FPDE 2005.

XML feed