Overview
========

This code implements the hygienic macro expansion algorithm in:

> Michael D. Adams. Towards the Essence of Hygiene. In Proceedings of
> the 42nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming
> Languages, POPL '15. ACM, New York, NY, USA, January 2015. ISBN
> 978-1-4503-3300-9. doi: 10.1145/2676726.2677013.

You can download a copy of that paper at: http://michaeldadams.org/papers/hygiene/

The repository for this code is at: https://bitbucket.org/mdmkolbe/towards-the-essence-of-hygiene-expander/

See the LICENSE file for licensing information.

In this README you will find instructions on running the tests and
directly invoking the expander.  When running the expander, please
take particular note of the limitations of this implementation
documented in the "Limitations" section of this README.

Finally, if you are interested in understanding the implementation of
this expander, you should take a quick look at the "Implementation"
section at the end of this README to help get you oriented.  Also, the
"Towards the Essence of Hygiene" paper explains the mathematical
foundations and motivations underlying this code and may be a useful
in understanding its overall design.


Running the tests
=================

To test this code, just load `tests.scm`.

The output should be:

    Running 'test0'
    Running 'test1'
    Running 'or-test0'
    Running 'or-test1'
    Running 'or-test2'
    Running 'or-test3'
    Running 'inc-test1'

If one of the tests fails, then `!!! FAILED !!!` will be printed under
the appropriate test.

You can run an individual test with `(run-test <test-name>)`.  For
example, `(run-test test0)`.  You can also get the input and expected
output of a test with `(test-input <test-name>)` and `(test-output
<test-name>)`.

This code has been tested under Chez Scheme 8.3 and Vicare Scheme 0.3d7.


Running the expander
====================

To directly run the expander, import the `(expand)` library and call
`(expand-s-expr #f env0 <s-expr>)` where the value of `<s-expr>` is
an s-expression containing the expression to expand.

You can replace `#f` with a non-negative integer for the maximum
number of expansion steps to take.

If you have a different set of core forms, you can replace `env0` with
a new default environment.  (Most people will not need to do this.)

You can directly run a particular test with `(expand-s-expr #f env0
(test-input <test-name>))`.

## S-expression notation ##

The `expand-s-expr` function uses s-expressions as input and output.
However, the expander operates on diatomic identifiers that contain
two atoms (which are represented by Scheme symbols) instead of one.
When these are equal to each other, we can just use the symbol to
stand for the diatomic identifier.  However, when they are different,
we use a vector notation `#(r b)` for an identifier with a reference
part of `r` and a binder part of `b`.

## Gensyms ##

During the process of expansion gensymed versions of atoms may be
created.  These use `@` and a number as a suffix (e.g. `foo@23`) so
you should make sure that none of the symbols in your input programs
contain `@`.

## Example ##

If you call the following

``` scheme
(expand-s-expr #f env0
  '(let-syntax ([and2 (lambda (stx)
                        (list #'if (cadr stx) (caddr stx) #'#f))])
    (and2 x y)))
```

then you should get something like the following

``` scheme
(let-syntax ([and2@50 (lambda (stx@51)
                        (list #'if (cadr stx@51) (caddr stx@51) #'#f))])
  (if x y '#f))
```

See `tests.scm` for more examples of code expansion.

## Low-level interface ##

The `expand-s-expr` function is a wrapper that presents a simplified
interface to the `expand-k-syntax*` function.  Specifically, it
automatically converts between the easier-to-read s-expr notation and
the k-syntax and u-syntax objects used internally.  If you want to
play with this internal representation, you should look at the
implementation of `expand-s-expr` to see how to call
`expand-k-syntax*`.

Limitations
===========

Main aim of this code is an implementation of the algorithm described
in "Towards the Essence of Hygiene".  For the sake of clarity, we make
several simplifications.

  - `syntax-case` is both a hygienic algorithm and a pattern matching
    form used with that algorithm.  This code just implements the
    hygienic expansion algorithm and does not implement pattern
    matching or the forms that go with it.

    Macros must thus use operations such as `null?`, `car`, `cdr`,
    `cons`, `free-identifier=?` and `bound-identifier=?` instead of
    `syntax-case`, `syntax-rules`, `quasisyntax` and `unsyntax`.

    The latter forms can actually be implemented as macros within the
    system implemented by this code.  They just have not been
    implemented yet.

  - Since we use `gensym` to create fresh atoms and gensyms are not a
    standardized feature, we implement our own version of `gensym`.
    We reserve the character `@` for this purpose and assume no
    non-gensymed symbols ever involve that character.

  - As in "Towards the Essence of Hygiene", we do not implement
    `datum->syntax`, `syntax->datum`, `define`, or `define-syntax`.

  - As in "Towards the Essence of Hygiene", the algorithm we implement
    is quadratic time though a full `syntax-case` implementation can
    be linear.

  - We directly implement the algorithm in the first half of "Towards
    the Essence of Hygiene" (i.e., the one using a gensym) instead of
    the nominal based implementation described in the latter half of
    "Towards the Essence of Hygiene".

  - We do not implement advanced macro features like modules, R6RS
    libraries or expand-time definitions (e.g. meta define).


Implementation
==============

If you want to understand the implementation, the main files you want
to read are `types.scm` so you understand the types being used and
`expand.scm` so you understand the expansion process.  Both of these
files include comments explaining the key ideas and code structure.
All other files are merely to support these two files.

Top-level files
---------------
 - `types.scm`: Defines the types used by the expander and basic
                operators for those types

 - `expand.scm`: The main code for the expander

 - `tests.scm`: Tests for the expander

 - `s-exprs.scm`: Types and operators for s-expr including functions
                  for injecting and projecting s-exprs to and from
                  k-syntax and u-syntax.

 - `expand-primitives.scm`: Primitives available to macro transformers

Utility libraries
-----------------
 - `util/gensym.scm`: Unique symbol generation

 - `util/record-match.scm`: Defines `match` and `define-match` forms for pattern matching records

 - `util/record-match-helpers.scm`: A helper library used by `util/record-match.scm`

 - `util/typed-records.scm`: Defines record definition forms that
                             check the types of the arguments to their
                             constructors