Update the README.

1 files changed, 351 insertions, 3 deletions

diff --git a/README.md b/README.md
index e37aa5d..e82a611 100644
--- a/README.md
+++ b/README.md
@@ -1,5 +1,353 @@
-# Cute scheme
+% Cute scheme design overview
+% Rose Hogenson; Cute scheme development team
+% April 22, 2022
+
+# 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 bytecode defined in encoding.csc. The bytecode
-interpreter is written in Rust.
+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.
+
+- **`<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.
+
+### Syntax-rules
+
+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.