path: root/README.md

# 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.

![Dorotya, the real-life Chromatopelma cyaneopubescens.](dorotya.jpg)

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.

![Code generation goes through several intermediate phases, named IR1,
IR2, and IR3.](design.svg)

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.