# Cute Scheme ## 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 Cute 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 The cute 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 2 such intermediate representations, not counting bytecode itself. These two languages are called IR1 and IR2. ### 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. - **``.** Constants are constant scheme expressions, often arising from quoted expressions. ``` (define-record-type (make-constant expression) constant? (expression constant-expression)) ``` - **``.** 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 (make-lexical-ref name gensym) lexical-ref? (name lexical-ref-name) (gensym lexical-ref-gensym)) ``` - **``.** The counterpart to ``, `` sets a lexically-bound variable. ``` (define-record-type (make-lexical-set name gensym expression) lexical-set? (name lexical-set-name) (gensym lexical-set-gensym) (expression lexical-set-expression)) ``` - **``.** 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 (make-library-define name expression library) library-define? (name library-define-name) (expression library-define-expression) (library library-define-library)) ``` - **``.** 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 (make-define-syntax name transformer) define-syntax? (name define-syntax-name) (transformer define-syntax-transformer)) ``` - **``.** The `` syntax is kind of self-explanatory, no? ``` (define-record-type (make-if test consequent alternate) if? (test if-test) (consequent if-consequent) (alternate if-alternate)) ``` - **``.** Call a procedure. ``` (define-record-type (make-call procedure arguments) call? (procedure call-procedure) (arguments call-arguments)) ``` - **``.** Evaluate two IR1 expressions in sequence. ``` (define-record-type (make-sequence head tail) sequence? (head sequence-head) (tail sequence-tail)) ``` - **``.** A closure. ``` (define-record-type (make-lambda body) lambda? (body lambda-body)) ``` - **``.** The design of `` is taken directly from Guile. A `lambda` expression will generate a `` with only one clause, but a `lambda-case` expression can of course generate `` syntax objects with more clauses. ``` (define-record-type (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)) ``` - **``.** A `` 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 (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 `` that stores the continuation explicitly. The syntax types for IR2 are given below. - **``.** An IR1 expression and its continuation. The expression is evaluated, and the result is passed to the continuation. ``` (define-record-type (make-atom expression continuation) atom? (expression atom-expression) (continuation atom-continuation)) ``` - **``.** 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 (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 `` and `` forms into `` which is a reference into the current closure. All `` forms will be replaced by a `` that explicitly captures variables from the parent context.