-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathREADME
195 lines (140 loc) · 6.87 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
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