bootstrap syntax-case and quasiquote using racket

[gelisam]

This PR provides two things: an idea for bootstrapping complex macros, and an example implementation of two such macros. The two macros are:

1. a syntax-case variant supporting keywords (e.g. else below), nested patterns, and matching on the rest of the list using ,xs ....
2. a variant of quasiquote which also supports ,xs ... for splicing-in a list.

Here is an example demonstrating those features:

(define-macros
  ([multiway-if
    (lambda (stx)
      (syntax-case stx (else)
        [(_ [else ,e])
         (pure e)]
        [(_ [,cond ,e] ,cases ...)
         (pure `(if cond e (multiway-if ,cases ...)))]))]))

Next, the idea. Theoretically it should be possible to implement many quality-of-life improvements as libraries, e.g. by writing a Klister macro implementing a fancy-syntax-case which supports nested patterns in terms of a primitive raw-syntax-case which does not. In practice, however, the lack of nested patterns makes raw-syntax-case so inconvenient that it makes that task very difficult. My idea is to make that task easier is to generate the Klister code which implementsfancy-syntax-case in terms of raw-syntax-case, and to write the code-generation tool in a more convenient language which does support nested patterns and more.

I chose Racket. Note that the task is now to generate the code for a Klister macro, it is not to define a Racket macro. Nevertheless, Racket's macros were very helpful, as I wrote myself a DSL making it easy to generate Klister code. The DSL looks like regular Klister code, augmented a with magic generate-syntax-case primitive which makes it look like Klister already supports nested pattern-matching.

[gelisam]

I care more about the idea than about the two macros. In particular, it's probably a good idea to provide nested patterns to the user in a different way, e.g. by providing functions converting between a Syntax and an ADT representation of a syntax object, as @david-christiansen suggested. But I think this Racket DSL will provide a good foundation for tackling any future bootstrapping issues we might encounter.

[gelisam]

Reviewers, don't be afraid of the +1,818 −218 summary, the actual diff is much smaller! The main addition is the +507 of bootstrap.rkt, plus +23 for two new helper functions in list-syntax.kl. The rest consists of +1,072 of generated code (I don't think bookstrap.rkt will change very often, so I think it's better to include the generated examples/dot-dot-dot.kl in the repository in order to avoid making Racket an extra requirement for building Klister), and the remaining +216 -507 consists of simplifications to other .kl files which previously had to use nested calls to syntax-case but can now use nested patterns.

[gelisam]

Note that this PR introduces a huge performance regression: the test suite used to pass in 16 seconds, but now it takes 63 seconds! I think this is partially because the generated dot-dot-dot.kl file is relatively large (1 KLOC) and takes 1.5 seconds to load. Multiplied by the 16 files which import it directly or indirectly, this accounts for half of the slowdown. I guess the other half is because fancy-syntax-case does more work than raw-syntax-case? Or maybe it generates code which does more work?

[gelisam]

@langston-barrett as discussed, this is the branch in which I am trying to define a variant of syntax-case which supports deep patterns. There is a lot of code in this branch already, but most of it is just to change the existing syntax-case calls to use the version which supports deep patterns, and the rest is some Racket code which I plan to delete anyway.

The reason I want to delete it is because it is needlessly repetitive, so I want to try a different approach. @david-christiansen suggested defining a Racket #lang which implements the Klister syntax, but during our call I said that I could not remember how that would help. I am happy to say that I have now figured out how it would help. To make sure I don't forget again, I wrote a document explaining my plan in detail:

https://github.com/gelisam/klister/blob/d2f9680d27a1e39d3df5012091cdecf37972c09f/bootstrap/README.md