The 90 Minute Scheme to C compiler

90 minute video presentation from Marc Feeley, along with accompanying PowerPoint slides and source code, for a Scheme to C compiler. Good discussion of continuations and closures, as well as some dipping into the area of compiler construction.

How to write a simple Scheme to C compiler, in Scheme. In only 90 minutes! And although not supporting the whole Scheme standard, the compiler supports fully optimized proper tail calls, continuations, and (of course) full closures. The compiler is implemented using two important compilation techniques for functional languages: closure conversion and CPS-conversion.

The emphasis is on the 4 major problem areas that crop up in an attempt to convert Scheme to C:

  • tail-calls a.k.a. tail-recursion opt.
  • first-class continuations
  • closures of indefinite extent
  • automatic memory management i.e. GC

The solution presented gives a series of source-to-source transformations. Stage 1 of the compiler expands the 'let' forms in the Scheme code. Stage 2 converts continuations to CPS. Stage 3 converts the code to closures using encapsulated closure objects. Stage 4 is not presented but touches on how the results would lend itself to a GC implementation.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Might want to consider hostin

Might want to consider hosting it at archive.org, or using bittorrent. Unless the hosting fees are fine.

It's a Univerté de Montréal site

So worst-case scenario, network admins there get a little upset. The bandwidth might not be that great, since Canadian Universities tend to have great links between themselves, but not-so-great links to the rest of the internet.

no sound?

I downloaded the two .avi files, but when QuickTime launched, there was no sound. QuickTime said the sound was in an unsupported format.

Had the same problem with Quicktime

Played ok under latest windows media player. Not sure what the problem with QT is.

divx

I just installed the free divx driver at divx.com and the audio and video work fine in QT.

AVI and MP3

I found out that the AVI format does not officially support MP3 audio, it's just a hack. So QuickTime for some reason hasn't added support for it. If the AVI is converted to a MOV, then it can work.

Lambda Lifting Question

In the video, the lecturer says that Lambda Lifting is not a general solution to the problem of representing closures. It seems to me like this would only be the case in languages which do not support currying. Am I correct in this assumption?

I imagine the problem's

I imagine the problem's mutable closures?