Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
blob: 804c44a8d15e75eb4b43a62ddb69f96bfe49c5c5 (plain)
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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
;;; Macro support for Rebirth Lisp
;;;
;;;  Copyright (C) 2017, 2018 Mike Gerwitz
;;;
;;;  This file is part of Gibble.
;;;
;;;  Gibble is free software: you can redistribute it and/or modify
;;;  it under the terms of the GNU Affero General Public License as
;;;  published by the Free Software Foundation, either version 3 of the
;;;  License, or (at your option) any later version.
;;;
;;;  This program is distributed in the hope that it will be useful,
;;;  but WITHOUT ANY WARRANTY; without even the implied warranty of
;;;  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;;;  GNU General Public License for more details.
;;;
;;;  You should have received a copy of the GNU Affero General Public License
;;;  along with this program.  If not, see <http://www.gnu.org/licenses/>.
;;;
;;; THIS IS BOOTSTRAP CODE INTENDED FOR USE ONLY IN REBIRTH.
;;;
;;;
;;;                           === STEP 1 ===
;;;
;;; Did you read Step 0 first?  If not, start there; see `rebirth.scm'.
;;;
;;; Without macro support, anything that involves producing code with
;;; variable structure at compile-time must be hard-coded in the
;;; compiler.  Perhaps the greatest power in Lisp is the ability to extend
;;; the language through its own facilities---its ability to parse itself
;;; and treat itself as data.
;;;
;;; So we need to introduce macro support.
;;;
;;; This is not a trivial task: RⁿRS has a rich and powerful system that
;;; would be quite a bit of work upfront to implement.  Instead, we're
;;; going to focus on traditional Lisp macros, which are conceptually
;;; rather simple---they produce a list that, when expanded, is treated as
;;; Lisp code as if the user had typed it herself.
;;;
;;; Macros hold the full power of Lisp---macro expansion _is_
;;; compilation.  This means that we need to compile macro expansions as
;;; their own separate programs during the normal compilation process and
;;; splice in the result.  But to execute the macro, we need to execute
;;; ECMAScript code that we just generated.  In other words: the evil eval.
;;;
;;; ECMAScript has two ways of evaluating ES code contained in a string:
;;; through the `eval' function and by instantiating `Function' with a
;;; string argument representing the body of the function (or something
;;; that can be cast into a string).  Good thing, otherwise we'd find
;;; ourselves painfully writing a Lisp interpreter in Rebirth Lisp.
;;;
;;; This implementation is very simple---there's very little code but a
;;; great deal of comments.  They describe important caveats and hopefully
;;; enlighten the curious reader.

(cond-expand
  (string->es
   (define (cdfn-macro sexp)
     (define (%make-macro-proc sexp)
       ;; The syntax for a macro definition is the same as a procedure
       ;; definition.  In fact, that's exactly what we want, since a macro is
       ;; a procedure that, when applied, produces a list.  But we want an
       ;; anonymous function, so override the id to the empty string.
       (let* ((proc-es (cdfn-proc sexp "")))
         ;; Rather than outputting the generated ES function, we're going to
         ;; immediately evaluate it.  This is a trivial task, but how we do
         ;; it is important: we need to maintain lexical scoping.  This
         ;; means that we must use `eval'---`new Function' does not create a
         ;; closure.
         ;;
         ;; The only thing we need to do to ensure that eval returns a
         ;; function is to enclose the function definition in
         ;; parenthesis.  This results in something along the lines of:
         ;;   eval("(function(args){...})")
         ;;
         ;; If you're confused by the execution environment (compiler
         ;; runtime vs. compiler output), don't worry, you're not
         ;; alone.  We're actually dealing with a number of things here:
         ;;
         ;;   1. Use `string->es' below to produce _compiler output_ for the
         ;;      next version of a Rebirth Lisp compiler that will be
         ;;      responsible for actually running the `eval'.
         ;;   2. That next version of the compiler will then compile
         ;;      ECMAScript function definition from macro procedure source
         ;;      using `cdfn-proc' as above.
         ;;   3. This will then be run by the compiler _at runtime_ by
         ;;      running the `eval' statement below (which is part of the
         ;;      program just as if it were Lisp).
         ;;   4. The result will be the procedure `proc-es' available to the
         ;;      compiler at runtime rather than produced as compiler output.
         ;;
         ;; There's a lot of words here for so little code!  We currently
         ;; lack the language features necessary to produce the types of
         ;; abstractions that would make this dissertation unnecessary.
         (string->es "eval('(' + $$proc$_$es + ')')")))

     ;; We then store the macro by name in memory in `_env.macros'.  When
     ;; invoked, it will apply the result of the above generated procedure
     ;; to `macro-compile-result' (defined below), which will produce the
     ;; ECMAScript code resulting from the macro application.
     ;;
     ;; There are consequences to this naive implementation.  Rebirth is a
     ;; dumb transpiler that relies on features of ECMAScript to do its
     ;; job.  In particular, we don't have any dependency graph or lexical
     ;; scoping or any of those necessary features---we let ECMAScript take
     ;; care of all of that.  That means that we have no idea what is
     ;; defined or even what has been compiled; we just transpile and move
     ;; on blindly.  Any errors resulting from undefined procedures, for
     ;; example, occur at runtime in the compiled output.
     ;;
     ;; These are features that will be implemented in Gibble Lisp; that's
     ;; not something to distract ourselves with now.
     ;;
     ;; So there are some corollaries:
     ;;
     ;;   1. Macros must be defined _before_ they are called.  Order
     ;;      matters.
     ;;   2. Macros can only make use of what is defined in the compiler
     ;;      runtime environment---if a procedure is defined, it won't be
     ;;      available to macros until the next compilation pass.  This is
     ;;      because we have no dependency graph and cannot automatically
     ;;      eval dependencies so that they are available in the execution
     ;;      context.
     ;;      - To work around that, procedures can be defined within the
     ;;        macro body.  Of course, then they're encapsulated within it,
     ;;        which is not always desirable.
     ;;
     ;; While this implementation is crippled, it does still provide good
     ;; foundation with which we can move forward.  Our use of recursive
     ;; Reⁿbirth passes and `cond-expand' makes this less of an issue as
     ;; well, since we're recursing anyway.
     (let ((macro-proc (%make-macro-proc sexp))
           (macro-id   (token-value (caadr sexp)))) ; XXX
       (string->es
        "_env.macros[$$macro$_$id] = function(){
           return $$macro$_$compile$_$result(
             $$macro$_$proc.apply(this,arguments))};")
       ;; Because the macro procedure was evaluated at runtime, it would
       ;; never actually itself be output.  This makes debugging difficult,
       ;; so we'll output it as a comment.  This is admittedly a little bit
       ;; dangerous, as we're assuming that no block comments will ever
       ;; appear in `macro-proc'.  But at the time of writing, this
       ;; assumption is perfectly valid.
       (string-append "/*macro " macro-id ": " macro-proc "*/")))


   ;; Compile the S-expression resulting from the macro application into
   ;; ECMAScript.
   ;;
   ;; This simply converts the given S-expression SEXP into an AST and
   ;; compiles it using the same procedures that we've been using for all
   ;; other code.  See below for details.
   (define (macro-compile-result sexp)
     (sexp->es (list->ast sexp)))


   ;; Produce a Rebirth List AST from an internal list form.
   ;;
   ;; Up until this point, the only way to represent Rebirth Lisp was using
   ;; a typical Lisp form.  With macros, however, we have bypassed that
   ;; source form---we're working with our own internal representation of a
   ;; list.
   ;;
   ;; The structure of the AST is already done---it mirrors that of the list
   ;; itself.  What we need to do is map over the list, recursively, and
   ;; convert each item into a token.
   ;;
   ;; Consider the tokens processed by `toks->ast': comments,
   ;; opening/closing delimiters, strings, and symbols. We don't need to
   ;; worry about comments since we aren't dealing with source code.  We
   ;; also don't need to worry about opening/closing delimiters since we
   ;; already have our list.  This leaves only two token types to worry
   ;; about: strings and symbols.
   ;;
   ;; And then there's the fascinating case of macro arguments.  When a
   ;; macro or procedure application are encountered during compilation, the
   ;; arguments are represented as tokens (see `apply-proc-or-macro').  As
   ;; just mentioned, the end goal is to convert our list SEXP into tokens
   ;; for the AST.  But the arguments are _already_ tokens, so they need no
   ;; additional processing---we just splice them in as-is!  This trivial
   ;; operation yields the powerful Lisp macro ability we're looking for:
   ;; the ability to pass around chunks of the AST.
   ;;
   ;; Consequently, we have Rebirth-specific syntax to deal with when
   ;; processing the AST within macros.  Up until this point, in place of
   ;; macros, we have used `fnmap', which operates on tokens.  That is the
   ;; case here as well: if a macro wishes to assert on or manipulate any
   ;; syntax it is given, it must use the Rebirth token API that the rest of
   ;; the system uses.  For example, say we have a macro `foo' that asserts
   ;; on its first argument as a string:
   ;;
   ;;   (foo "moo") => "cow"
   ;;   (foo "bar") => "baz"
   ;;
   ;; This will _not_ work:
   ;;
   ;;   (define-macro (foo x)
   ;;     (if (string=? x "moo") "cow" "baz"))
   ;;
   ;; The reason is that `x' is not a string---it is a `token?'.  Instead,
   ;; we must do this:
   ;;
   ;;   (define-macro (foo x)
   ;;     (if (string=? (token-value x) "moo") "cow" "baz"))
   ;;
   ;; Of course, if you do not need to make that determination at
   ;; compile-time, you can defer it to runtime instead and use `string=?':
   ;;
   ;;   (define-macro (foo x)
   ;;     (quasiquote (if (string=? (unquote x) "moo") "cow" "baz")))
   ;;
   ;; Simple implementation, complex consequences.  Scheme uses syntax
   ;; objects; we'll provide that abstraction over our implementation at
   ;; some point.
   ;;
   ;; Okay!  That's trivial enough, isn't it?
   (define (list->ast sexp)
     ;; Anything that is not a string is considered to be a symbol
     ;; token.  But note that a symbol token does not necessarily mean an
     ;; ECMAScript Symbol object.
     (define (%list-item item)
       (case (es:typeof item)
         (("string")
          (list "string" item))
         (("symbol")
          (list "symbol" (string->es "Symbol.keyFor($$item)")))
         (else
          (list "symbol" (string->es "''+$$item")))))

     ;; Recursively create tokens for each item.  Note that we will not have
     ;; any useful source code or source location information---just use the
     ;; empty string and 0 for them, respectively.
     ;;
     ;; The lexeme will simply be the item converted into a string, whatever
     ;; that happens to be.
     (if (token? sexp)
         sexp
         (if (list? sexp)
             (map list->ast sexp)
             (let* ((item-parts (%list-item sexp))
                    (type       (car item-parts))
                    (lexeme     (cadr item-parts)))
               (car (make-token type lexeme "" 0))))))))