Call With Current Continuation

17 Sep 2014

I’ve started this blog to write about the scheme compiler I’m writing with some friends.

Why a scheme compiler?

I love the simplicity of scheme (e.g. R5RS) as well as well as how expressive it is.

Syntax

S-expressions

The syntax of the language is based on s-expressions which are generated by the grammar

<s-expr> ::= <symbol> | (<s-expr> . <s-expr>)

Symbols can be called anything! Lists (a . (b . (c . ()))) may be written flattened (a b c) and there is a little syntactic-sugar for lists made out of pairs, additions for things like characters (#\x, #\newline), booleans (#t, #f) and short hands:

'exp  for  (quote exp)
`exp  for  (quasiquote exp)
,exp  for  (unquote exp)

but that’s it!

(Special) forms

Using this syntax we have expressions for defining names, creating procedures, applying them:

(define (lambda ( ...) <body> ...) ( ...)

It’s also possible to take any lisp code and “quote” it so that it’s data you can operate on rather than program code that gets executed. Quasiquote gives finer control over this, similar to multi stage programming.

Macros

Scheme also has a macro-expansion stage and enables you to define your own macros. This lets you write programs that operate on program source code at compile time - useful for adding new language constructs or even creating whole new languages embedded into scheme, for example miniKanren.

Lambda the ultimate

Essentially everything in the language can be modelled by lambda. Procedurs which can be used to name and pass around bits of program code or for abstraction, but also data structures (by closing over free variables), control flow (by means of continuations) and recursion (the Y combinator).

I think that Scheme was the first language to fully commit to lexical scope - which is basically the norm in programming languages now. Lexical scoping is the name for how lambda binds variables. It is central to the language and even schemes hygienic macros take it into account - unlike most languages with macro systems!

Since lambda is so powerful and has so many different uses, it has been said that it is the scheme implementors job to implement the different uses efficiently.

A Compiler?

I feel like there’s a big difference in knowing something and actually doing it. A long time ago I watched Marc Feeley’s “scheme to C in 90 mins” talk and read the slides - he showed the overall strategy of compiling scheme to C. I’ve written toy compilers before but they aren’t quite as big a deal as tackling something like a bootstrapping scheme compiler.

I want to get experience in writing a real-ish compiler before getting into some more advanced thing programming language things like partial evaluation. For this project I decided to target C instead of assembly so I don’t have to handle register coloring or allocation - I hope that trying to make things easier on myself this way wont slow things down too much to make it unmanagable.

I’ve tried really hard at this already, twice. This time I really hope I can succeed!