Chromatopelma scheme compiler

Background

Scheme is a simple language, and has a number of open specifications. These two qualities make it a popular target for hobby compilers. The language design consists of a small number of primitives, and a focus on implementing features through the powerful macro system.

The strength of scheme is its flexibility and power of introspection. The eval procedure gives programs the full power of the compiler at runtime. For a program that uses eval, it will by necessity need to have the full compiler bundled as part of the runtime. My goal is to write a self-hosting scheme compiler targeting a minimal bytecode.

Objective

Chromatopelma scheme is a partial r7rs implementation with a focus on ease of implementation and a reusable library. The frontend is written in r7rs Scheme, and compiles to a minimal bytecode.

Detailed design

I started this project as a way to get familiar with writing a compiler for a functional language. My goal was to write a self-hosting compiler, and my candidate languages were SML or scheme. I picked scheme because of my love for parentheses, but at times I'm missing static typing.

Chromatopelma cyaneopubescens is a kind of tarantula native to Venezuela. Fig. 1 shows Dorotya going after a roach.

The Chromatopelma scheme compiler (like most compilers) consists of a number of phases that gradually transform a program from scheme code through numerous intermediate representations. The csc compiler has 3 such intermediate representations, not counting bytecode itself. These languages are creatively called IR1, IR2, and IR3.

Fig. 2 shows the phases of code generation. Code generation goes through several intermediate phases, named IR1, IR2, and IR3.

IR1

IR1 can be thought of as scheme code with all the macros expanded. An IR1 program or library is a tree structure composed of one of a few basic syntax types.

The builtin forms of IR1 are described below.

• <constant>. Constants are constant scheme expressions, often arising from quoted expressions.

(define-record-type <constant> (make-constant expression) constant? (expression constant-expression))

• <lexical-ref>. One of a few ref types, a lexical ref is a reference to a lexically bound variable, introduced by a lambda or let form.

(define-record-type <lexical-ref> (make-lexical-ref name gensym) lexical-ref? (name lexical-ref-name) (gensym lexical-ref-gensym))

• <lexical-set>. The counterpart to <lexical-ref>, <lexical-set> sets a lexically-bound variable.

(define-record-type <lexical-set> (make-lexical-set name gensym expression) lexical-set? (name lexical-set-name) (gensym lexical-set-gensym) (expression lexical-set-expression))

• <library-define>. Library-define defines a variable in a library. This form is introduced by the builtin define procedure, and the current library is attached to disambiguate names in different libraries.

(define-record-type <library-define> (make-library-define name expression library) library-define? (name library-define-name) (expression library-define-expression) (library library-define-library))

• <define-syntax>. Defines a syntax transformer in the current library. Even though IR1 has all the macros expanded, we need to keep any syntax transformer definitions around with the compiled library.

(define-record-type <define-syntax> (make-define-syntax name transformer) define-syntax? (name define-syntax-name) (transformer define-syntax-transformer))

• <if>. The <if> syntax is kind of self-explanatory, no?

(define-record-type <if> (make-if test consequent alternate) if? (test if-test) (consequent if-consequent) (alternate if-alternate))

• <call>. Call a procedure.

(define-record-type <call> (make-call procedure arguments) call? (procedure call-procedure) (arguments call-arguments))

• <sequence>. Evaluate two IR1 expressions in sequence.

(define-record-type <sequence> (make-sequence head tail) sequence? (head sequence-head) (tail sequence-tail))

• <lambda>. A closure.

(define-record-type <lambda> (make-lambda body) lambda? (body lambda-body))

• <lambda-case>. The design of <lambda-case> is taken directly from Guile. A lambda expression will generate a <lambda-case> with only one clause, but a lambda-case expression can of course generate <lambda-case> syntax objects with more clauses.

(define-record-type <lambda-case> (make-lambda-case arguments rest gensyms body alternate) lambda-case? (arguments lambda-case-arguments) (rest lambda-case-rest) (gensyms lambda-case-gensyms) (body lambda-case-body) (alternate lambda-case-alternate))

• <letrec>. A <letrec> expression defines a number of lexical variables. This can result from a letrec or letrec* expression. If it was a letrec*, in-order? will be true.

(define-record-type <letrec> (make-letrec in-order? names gensyms values expression) letrec? (in-order? letrec-in-order?) (names letrec-names) (gensyms letrec-gensyms) (values letrec-values) (expression letrec-expression))

And that's all the IR1 types. The design of the macro expander is sketched briefly below.

Macro expansion

Macro expansion essentially consists of a compiler from scheme code to IR1. As the compiler walks the input scheme expression, it holds an environment which maps symbols to lexically bound variables, syntax transformers, and library references from imports. A syntax transformer is a procedure taking a scheme expression and returning an IR1 expression. This means that when the macro expander encounters a syntax-rules form, it will generate a lambda expression that transforms its input according to the syntax transformer.

Generally, the macro transformer walks the input expression recursively. If it finds something that looks like a macro invocation, it will invoke the appropriate syntax transformer and just return the result. If the expression doesn't look like a macro invocation, it could be a procedure call, a constant, or a variable reference. Either way it will get compiled to the corresponding IR1 construct.

The syntax-rules syntax transformer takes as input a syntax-rules form, and the output is a syntax transformer. Recall that a syntax transformer accepts a scheme expression and emits IR1. In this way, syntax-rules can be thought of as a curried function accepting a syntax-rules form, and an expression to be transformed by these syntax rules.

There are complex rules for maintaining hygiene. I will quote extensively from R6RS here.

Operationally, the expander can maintain hygiene with the help of marks and substitutions. Marks are applied selectively by the expander to the output of each transformer it invokes, and substitutions are applied to the portions of each binding form that are supposed to be within the scope of the bound identifiers. Marks are used to distinguish like-named identifiers that are introduced at different times (either present in the source or introduced into the output of a particular transformer call), and substitutions are used to map identifiers to their expand-time values.

Each time the expander encounters a macro use, it applies an antimark to the input form, invokes the associated transformer, then applies a fresh mark to the output. Marks and antimarks cancel, so the portions of the input that appear in the output are effectively left unmarked, while the portions of the output that are introduced are marked with the fresh mark.

Each time the expander encounters a binding form it creates a set of substitutions, each mapping one of the (possibly marked) bound identifiers to information about the binding. (For a lambda expression, the expander might map each bound identifier to a representation of the formal parameter in the output of the expander. For a let-syntax form, the expander might map each bound identifier to the associated transformer.) These substitutions are applied to the portions of the input form in which the binding is supposed to be visible.

Marks and substitutions together form a wrap that is layered on the form being processed by the expander and pushed down toward the leaves as necessary. A wrapped form is referred to as a wrapped syntax object. Ultimately, the wrap may rest on a leaf that represents an identifier, in which case the wrapped syntax object is also referred to as an identifier. An identifier contains a name along with the wrap. (Names are typically represented by symbols.)

When a substitution is created to map an identifier to an expand-time value, the substitution records the name of the identifier and the set of marks that have been applied to that identifier, along with the associated expand-time value. The expander resolves identifier references by looking for the latest matching substitution to be applied to the identifier, i.e., the outermost substitution in the wrap whose name and marks match the name and marks recorded in the substitution. The name matches if it is the same name (if using symbols, then by eq?), and the marks match if the marks recorded with the substitution are the same as those that appear below the substitution in the wrap, i.e., those that were applied before the substitution. Marks applied after a substitution, i.e., appear over the substitution in the wrap, are not relevant and are ignored.

—R6RS libraries pp. 50–51

I can't claim to understand everything in the above quote, but I'll try to summarize as best I can. The point of a wrap is that when an expression is inserted by a macro, it should use the environment that was present at the macro definition time, that way any variable references are to the variables visible where the macros was defined. To support this, csc uses a syntax-case macro inspired by the syntax-case from R6RS. The syntax-case macro is internal-only, and is not provided in csc code. Basically syntax-case pattern-matches on a scheme expression, transparently passing the wrap down to the sub-expressions.

Now let's talk about marks. The point of marks is to disambiguate between different symbols with the same name introduced by different invocations of a macro. To briefly demonstrate the point of marks, consider the following code snippet

(define-syntax set-b
  (syntax-rules ()
    ((set-b) (define b 10))))
(define b 5)
(set-b)
(write b)

Will this print 5 or 10? Anyone familiar with hygienic macros will know the answer should be 5. The syntax transformer set-b, although it captures the same top-level environment in the wrap, does not insert a definition of b into its environment. Let's see how the situation looks with marks. When the expander expands (set-b), it applies an antimark to the input form. Not much to see here, the input form is just the macro name. Then it expands the macro invocation first into (define b 10), and applies a mark to this form. The mark will get propagated to the leaves by syntax-case, meaning the symbol that is defined isn't b, but b with a mark. All marks get a unique ID. This is the condition that ensures hygiene.

Now here's the part that I'm not sure about:

The name matches if it is the same name (if using symbols, then by eq?), and the marks match if the marks recorded with the substitution are the same as those that appear below the substitution in the wrap, i.e., those that were applied before the substitution. Marks applied after a substitution, i.e., appear over the substitution in the wrap, are not relevant and are ignored.

For now the strategy that csc is using is that symbols are equal if their marks are the same, or if one of the symbols has no marks and the names are equal. This takes care of the case where a macro references a variable that was in-scope when the macro was defined. It's possible that this behavior isn't quite right for macros that generate other macros, but the above paragraph is breaking my brain.

IR2

IR2 is what is known as "continuation passing style". When I learned about continuation passing style in school, we learned that it's possible to write code in CPS, but never discussed why you would want to, or the application to compilers. The point, I now realize, is to support arbitrary control flow created by call-with-current-continuation. IR2 shares a lot with IR1. The main difference is that call/cc has its own construct, and most expressions are wrapped in a <continue> that stores the continuation explicitly.

The syntax types for IR2 are given below.

• <atom>. An IR1 expression and its continuation. The expression is evaluated, and the result is passed to the continuation.

(define-record-type <atom> (make-atom expression continuation) atom? (expression atom-expression) (continuation atom-continuation))

• <call/cc>. This is call-with-current-continuation. It takes two continuations, the first is called immediately with a function that returns to the second continuation.

(define-record-type <call/cc> (make-call/cc expression continuation) call/cc? (expression call/cc-expression) (continuation call/cc-continuation))

IR3

I've only just started thinking about IR3, but it's the closure conversion step for IR2. Afterwards, we will transform all <lexical-ref> and <library-ref> forms into <closure-ref> which is a reference into the current closure. All <lambda> forms will be replaced by a <closure> that explicitly captures variables from the parent context.

Build process

The idea behind the build process is to bootstrap compilation through a Guile compatibility layer. Because we're writing R7RS scheme, Guile can execute csc just fine. So building executes in phases.

1. Use Guile to run the compiler on itself, producing a compiled bytecode blob.
2. Run the bytecode blob on the compiler again, producing a second blob that would in theory be identical.
3. Embed the compiler bytecode blob with the bytecode interpreter to make a compiler executable.

CLI interface

The csc compiler has a simple CLI interface. There are two main modes of operation, compile-and-run, and ahead-of-time compilation. The default is compile-and-run.

The compiler flags are given below.

• -I dir. Add dir to the list of directories to be searched for libraries. A system directory will always be searched as well. A library name is translated into a path by combining the elements with /. Library files end in a .csc suffix, and if there is a .cso precomipled object file in the same directory, it will be used instead of the .csc source file. Indeed, the .csc source file is not required at all if a precompiled object file is found.
• -o file. Write a precompiled object file to file. If -o is specified, csc will operate in ahead-of-time compilation mode and will not run the program. The output file will usually end in .cso. This option can be used to precompile libraries to speed up execution, and is used by the build process to turn the compiler into a bytecode blob that can be embedded with the bytecode interpreter.

The csc compiler also takes a filename to compile and possibly execute.