Martin Geisler Online

I had my first exam in this semester today, I’ve passed DAIMI:dOvs — the compilation course — with the grade 13! The exam went much better than I had hoped, let me explain why…

The main part of DAIMI:dOvs is to write two major programs: a compiler in ML that will compile a dialect of Scheme called DAIMI-Scheme into bytecode; and a virtual machine written in C which will execute the bytecode. Using this compiler and VM we then have to BootStrap a compiler given to us by our lecturer Olivier Danvy written in DAIMI-Scheme.

As the project went along Lars Petersen ended up writing a majority of the compiler and Thomas Mølhave ended up writing and designing most of the VM, especially the rewritten (and much better) second version. I coded a bit here and a bit there, made some infrastructure such as a cool Makefile, began the report and so on… The result was that I didn’t really have any major code which I could say: this is my code — I’ve designed it and I know every little detail in it. Both Lars and Thomas could do that with the compiler and the VM, respectively.

At the exam I started talking about garbage collectors — a pretty easy subject with lots to talk about. But that question was just for warming up. The real questions would come afterwards — Danvy started with a question about how one could change the parameter passing semantics in DAIMI-Scheme from eager to lazy evaluation. And that was just soo lucky, for I had in fact been looking at just that: I had spend the last couple of days just before the deadline trying to implement this as an extra feature in our compiler — Danvy picked the one bit of code that was mine!

So I started talking about lazy evaluation, first I defined it and compared it against the normal eager evaluation we’re all familiar with from languages like Pascal, C, Scheme, ML, etc. Lazy evaluation can be simulated “by hand” in most functional languages, but it’s builtin in a language like Haskell. I wanted to have our compiler compile a program like

(define first (lambda (a b) a))
(first (quotient 4 2) (quotient 2 0))

into a program that behaves like this one

(define quotient (let ([original quotient])
                   (lambda (a b)
                     (original (a) (b)))))
(define first (lambda (a b) (a)))
(first (lambda () (quotient (lambda () 4) (lambda () 2)))
       (lambda () (quotient (lambda () 2) (lambda () 0))))

This program will, when compiled like any other program, run without the normal runtime error caused by the division by zero in the second argument because the evaluation of the argument has been delayed.

I fiddled with this for a couple of days, and managed to get 270 out of 300 tests working, including the example above. But it was never prefect, but it was certainly good enough so that I could talk about it to the exam :-)

After having talked about the lazy extension, we talked abit about our optimizations — it turned out that there is a subtle error in it because our inliner will inline strings in the code. The inlined strings will then be assigned different locations in the store, making the eqv? function say that they are different, when infact they should be the same:

(define x "foo")
(eqv? x x)

is turned into just

(eqv? "foo" "foo")

which suddenly returns #f, that is, false, when it should return true. I could understand the problem when the censor explained it to me, but I quickly blamed Lars for it… :-)

The next exam will be a written exam in DAIMI:dSprogSem the 13th. Wish me luck!