Commit | Line | Data |
---|---|---|
5161a3c0 AW |
1 | ;;; -*- mode: scheme; coding: utf-8; -*- |
2 | ||
747bd534 | 3 | ;;;; Copyright (C) 2009, 2010, 2011, 2012, 2013 Free Software Foundation, Inc. |
5161a3c0 AW |
4 | ;;;; |
5 | ;;;; This library is free software; you can redistribute it and/or | |
6 | ;;;; modify it under the terms of the GNU Lesser General Public | |
7 | ;;;; License as published by the Free Software Foundation; either | |
8 | ;;;; version 3 of the License, or (at your option) any later version. | |
9 | ;;;; | |
10 | ;;;; This library is distributed in the hope that it will be useful, | |
11 | ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | ;;;; Lesser General Public License for more details. | |
14 | ;;;; | |
15 | ;;;; You should have received a copy of the GNU Lesser General Public | |
16 | ;;;; License along with this library; if not, write to the Free Software | |
17 | ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
18 | ;;;; | |
19 | ||
20 | \f | |
21 | ||
22 | ;;; Commentary: | |
23 | ||
b2b554ef AW |
24 | ;;; Scheme eval, written in Scheme. |
25 | ;;; | |
26 | ;;; Expressions are first expanded, by the syntax expander (i.e. | |
27 | ;;; psyntax), then memoized into internal forms. The evaluator itself | |
28 | ;;; only operates on the internal forms ("memoized expressions"). | |
29 | ;;; | |
30 | ;;; Environments are represented as linked lists of the form (VAL ... . | |
31 | ;;; MOD). If MOD is #f, it means the environment was captured before | |
32 | ;;; modules were booted. If MOD is the literal value '(), we are | |
33 | ;;; evaluating at the top level, and so should track changes to the | |
34 | ;;; current module. | |
35 | ;;; | |
36 | ;;; Evaluate this in Emacs to make code indentation work right: | |
37 | ;;; | |
38 | ;;; (put 'memoized-expression-case 'scheme-indent-function 1) | |
5161a3c0 AW |
39 | ;;; |
40 | ||
41 | ;;; Code: | |
42 | ||
43 | \f | |
44 | ||
5161a3c0 AW |
45 | (eval-when (compile) |
46 | (define-syntax capture-env | |
47 | (syntax-rules () | |
bb0c8157 AW |
48 | ((_ (exp ...)) |
49 | (let ((env (exp ...))) | |
50 | (capture-env env))) | |
5161a3c0 AW |
51 | ((_ env) |
52 | (if (null? env) | |
53 | (current-module) | |
54 | (if (not env) | |
b2b554ef AW |
55 | ;; the and current-module checks that modules are booted, |
56 | ;; and thus the-root-module is defined | |
5f161164 | 57 | (and (current-module) the-root-module) |
5161a3c0 AW |
58 | env))))) |
59 | ||
d8a071fc AW |
60 | ;; Fast case for procedures with fixed arities. |
61 | (define-syntax make-fixed-closure | |
4abb824c | 62 | (lambda (x) |
9331f91c | 63 | (define *max-static-argument-count* 8) |
4abb824c AW |
64 | (define (make-formals n) |
65 | (map (lambda (i) | |
66 | (datum->syntax | |
c438cd71 | 67 | x |
4abb824c AW |
68 | (string->symbol |
69 | (string (integer->char (+ (char->integer #\a) i)))))) | |
70 | (iota n))) | |
71 | (syntax-case x () | |
d8a071fc | 72 | ((_ eval nreq body env) (not (identifier? #'env)) |
4abb824c | 73 | #'(let ((e env)) |
d8a071fc AW |
74 | (make-fixed-closure eval nreq body e))) |
75 | ((_ eval nreq body env) | |
4abb824c AW |
76 | #`(case nreq |
77 | #,@(map (lambda (nreq) | |
78 | (let ((formals (make-formals nreq))) | |
79 | #`((#,nreq) | |
d8a071fc AW |
80 | (lambda (#,@formals) |
81 | (eval body | |
82 | (cons* #,@(reverse formals) env)))))) | |
4abb824c AW |
83 | (iota *max-static-argument-count*)) |
84 | (else | |
85 | #,(let ((formals (make-formals *max-static-argument-count*))) | |
86 | #`(lambda (#,@formals . more) | |
87 | (let lp ((new-env (cons* #,@(reverse formals) env)) | |
88 | (nreq (- nreq #,*max-static-argument-count*)) | |
89 | (args more)) | |
90 | (if (zero? nreq) | |
91 | (eval body | |
d8a071fc AW |
92 | (if (null? args) |
93 | new-env | |
94 | (scm-error 'wrong-number-of-args | |
95 | "eval" "Wrong number of arguments" | |
96 | '() #f))) | |
4abb824c AW |
97 | (if (null? args) |
98 | (scm-error 'wrong-number-of-args | |
99 | "eval" "Wrong number of arguments" | |
100 | '() #f) | |
101 | (lp (cons (car args) new-env) | |
102 | (1- nreq) | |
103 | (cdr args))))))))))))) | |
104 | ||
a4b64fa2 AW |
105 | ;; Fast case for procedures with fixed arities and a rest argument. |
106 | (define-syntax make-rest-closure | |
107 | (lambda (x) | |
108 | (define *max-static-argument-count* 3) | |
109 | (define (make-formals n) | |
110 | (map (lambda (i) | |
111 | (datum->syntax | |
112 | x | |
113 | (string->symbol | |
114 | (string (integer->char (+ (char->integer #\a) i)))))) | |
115 | (iota n))) | |
116 | (syntax-case x () | |
117 | ((_ eval nreq body env) (not (identifier? #'env)) | |
118 | #'(let ((e env)) | |
119 | (make-rest-closure eval nreq body e))) | |
120 | ((_ eval nreq body env) | |
121 | #`(case nreq | |
122 | #,@(map (lambda (nreq) | |
123 | (let ((formals (make-formals nreq))) | |
124 | #`((#,nreq) | |
125 | (lambda (#,@formals . rest) | |
126 | (eval body | |
127 | (cons* rest #,@(reverse formals) env)))))) | |
128 | (iota *max-static-argument-count*)) | |
129 | (else | |
130 | #,(let ((formals (make-formals *max-static-argument-count*))) | |
131 | #`(lambda (#,@formals . more) | |
132 | (let lp ((new-env (cons* #,@(reverse formals) env)) | |
133 | (nreq (- nreq #,*max-static-argument-count*)) | |
134 | (args more)) | |
135 | (if (zero? nreq) | |
136 | (eval body (cons args new-env)) | |
137 | (if (null? args) | |
138 | (scm-error 'wrong-number-of-args | |
139 | "eval" "Wrong number of arguments" | |
140 | '() #f) | |
141 | (lp (cons (car args) new-env) | |
142 | (1- nreq) | |
143 | (cdr args))))))))))))) | |
144 | ||
9331f91c AW |
145 | (define-syntax call |
146 | (lambda (x) | |
147 | (define *max-static-call-count* 4) | |
148 | (syntax-case x () | |
149 | ((_ eval proc nargs args env) (identifier? #'env) | |
150 | #`(case nargs | |
151 | #,@(map (lambda (nargs) | |
152 | #`((#,nargs) | |
153 | (proc | |
154 | #,@(map | |
155 | (lambda (n) | |
156 | (let lp ((n n) (args #'args)) | |
157 | (if (zero? n) | |
158 | #`(eval (car #,args) env) | |
159 | (lp (1- n) #`(cdr #,args))))) | |
160 | (iota nargs))))) | |
161 | (iota *max-static-call-count*)) | |
162 | (else | |
163 | (apply proc | |
164 | #,@(map | |
165 | (lambda (n) | |
166 | (let lp ((n n) (args #'args)) | |
167 | (if (zero? n) | |
168 | #`(eval (car #,args) env) | |
169 | (lp (1- n) #`(cdr #,args))))) | |
170 | (iota *max-static-call-count*)) | |
171 | (let lp ((exps #,(let lp ((n *max-static-call-count*) | |
172 | (args #'args)) | |
173 | (if (zero? n) | |
174 | args | |
175 | (lp (1- n) #`(cdr #,args))))) | |
176 | (args '())) | |
177 | (if (null? exps) | |
178 | (reverse args) | |
179 | (lp (cdr exps) | |
180 | (cons (eval (car exps) env) args))))))))))) | |
181 | ||
b2b554ef AW |
182 | ;; This macro could be more straightforward if the compiler had better |
183 | ;; copy propagation. As it is we do some copy propagation by hand. | |
5161a3c0 AW |
184 | (define-syntax mx-bind |
185 | (lambda (x) | |
186 | (syntax-case x () | |
187 | ((_ data () body) | |
188 | #'body) | |
189 | ((_ data (a . b) body) (and (identifier? #'a) (identifier? #'b)) | |
190 | #'(let ((a (car data)) | |
191 | (b (cdr data))) | |
192 | body)) | |
193 | ((_ data (a . b) body) (identifier? #'a) | |
194 | #'(let ((a (car data)) | |
195 | (xb (cdr data))) | |
196 | (mx-bind xb b body))) | |
197 | ((_ data (a . b) body) | |
198 | #'(let ((xa (car data)) | |
199 | (xb (cdr data))) | |
200 | (mx-bind xa a (mx-bind xb b body)))) | |
201 | ((_ data v body) (identifier? #'v) | |
202 | #'(let ((v data)) | |
203 | body))))) | |
204 | ||
b2b554ef AW |
205 | ;; The resulting nested if statements will be an O(n) dispatch. Once |
206 | ;; we compile `case' effectively, this situation will improve. | |
5161a3c0 AW |
207 | (define-syntax mx-match |
208 | (lambda (x) | |
209 | (syntax-case x (quote) | |
210 | ((_ mx data tag) | |
211 | #'(error "what" mx)) | |
212 | ((_ mx data tag (('type pat) body) c* ...) | |
213 | #`(if (eqv? tag #,(or (memoized-typecode (syntax->datum #'type)) | |
214 | (error "not a typecode" #'type))) | |
215 | (mx-bind data pat body) | |
216 | (mx-match mx data tag c* ...)))))) | |
217 | ||
218 | (define-syntax memoized-expression-case | |
219 | (lambda (x) | |
220 | (syntax-case x () | |
221 | ((_ mx c ...) | |
222 | #'(let ((tag (memoized-expression-typecode mx)) | |
223 | (data (memoized-expression-data mx))) | |
224 | (mx-match mx data tag c ...))))))) | |
225 | ||
226 | ||
21ec0bd9 AW |
227 | ;;; |
228 | ;;; On 18 Feb 2010, I did a profile of how often the various memoized expression | |
229 | ;;; types occur when getting to a prompt on a fresh build. Here are the numbers | |
230 | ;;; I got: | |
231 | ;;; | |
232 | ;;; lexical-ref: 32933054 | |
233 | ;;; call: 20281547 | |
234 | ;;; toplevel-ref: 13228724 | |
235 | ;;; if: 9156156 | |
236 | ;;; quote: 6610137 | |
237 | ;;; let: 2619707 | |
238 | ;;; lambda: 1010921 | |
239 | ;;; begin: 948945 | |
240 | ;;; lexical-set: 509862 | |
241 | ;;; call-with-values: 139668 | |
242 | ;;; apply: 49402 | |
243 | ;;; module-ref: 14468 | |
244 | ;;; define: 1259 | |
245 | ;;; toplevel-set: 328 | |
21ec0bd9 AW |
246 | ;;; call/cc: 0 |
247 | ;;; module-set: 0 | |
248 | ;;; | |
249 | ;;; So until we compile `case' into a computed goto, we'll order the clauses in | |
250 | ;;; `eval' in this order, to put the most frequent cases first. | |
251 | ;;; | |
252 | ||
5161a3c0 AW |
253 | (define primitive-eval |
254 | (let () | |
a4b64fa2 AW |
255 | ;; We pre-generate procedures with fixed arities, up to some number |
256 | ;; of arguments, and some rest arities; see make-fixed-closure and | |
257 | ;; make-rest-closure above. | |
d8a071fc AW |
258 | |
259 | ;; A unique marker for unbound keywords. | |
260 | (define unbound-arg (list 'unbound-arg)) | |
261 | ||
7572ee52 AW |
262 | ;; Procedures with rest, optional, or keyword arguments, potentially with |
263 | ;; multiple arities, as with case-lambda. | |
d8a071fc | 264 | (define (make-general-closure env body nreq rest? nopt kw inits alt) |
7572ee52 | 265 | (define alt-proc |
a4b64fa2 | 266 | (and alt ; (body docstring nreq ...) |
dc3e203e | 267 | (let* ((body (car alt)) |
c438cd71 LC |
268 | (spec (cddr alt)) |
269 | (nreq (car spec)) | |
270 | (rest (if (null? (cdr spec)) #f (cadr spec))) | |
271 | (tail (and (pair? (cdr spec)) (pair? (cddr spec)) (cddr spec))) | |
dc3e203e AW |
272 | (nopt (if tail (car tail) 0)) |
273 | (kw (and tail (cadr tail))) | |
274 | (inits (if tail (caddr tail) '())) | |
275 | (alt (and tail (cadddr tail)))) | |
276 | (make-general-closure env body nreq rest nopt kw inits alt)))) | |
f3cf9421 AW |
277 | (define (set-procedure-arity! proc) |
278 | (let lp ((alt alt) (nreq nreq) (nopt nopt) (rest? rest?)) | |
279 | (if (not alt) | |
fc835b1b AW |
280 | (begin |
281 | (set-procedure-property! proc 'arglist | |
282 | (list nreq | |
283 | nopt | |
284 | (if kw (cdr kw) '()) | |
285 | (and kw (car kw)) | |
286 | (and rest? '_))) | |
287 | (set-procedure-minimum-arity! proc nreq nopt rest?)) | |
c438cd71 LC |
288 | (let* ((spec (cddr alt)) |
289 | (nreq* (car spec)) | |
290 | (rest?* (if (null? (cdr spec)) #f (cadr spec))) | |
291 | (tail (and (pair? (cdr spec)) (pair? (cddr spec)) (cddr spec))) | |
f3cf9421 AW |
292 | (nopt* (if tail (car tail) 0)) |
293 | (alt* (and tail (cadddr tail)))) | |
294 | (if (or (< nreq* nreq) | |
295 | (and (= nreq* nreq) | |
296 | (if rest? | |
297 | (and rest?* (> nopt* nopt)) | |
298 | (or rest?* (> nopt* nopt))))) | |
299 | (lp alt* nreq* nopt* rest?*) | |
300 | (lp alt* nreq nopt rest?))))) | |
301 | proc) | |
302 | (set-procedure-arity! | |
303 | (lambda %args | |
304 | (let lp ((env env) | |
305 | (nreq* nreq) | |
306 | (args %args)) | |
307 | (if (> nreq* 0) | |
308 | ;; First, bind required arguments. | |
309 | (if (null? args) | |
310 | (if alt | |
311 | (apply alt-proc %args) | |
312 | (scm-error 'wrong-number-of-args | |
313 | "eval" "Wrong number of arguments" | |
314 | '() #f)) | |
315 | (lp (cons (car args) env) | |
316 | (1- nreq*) | |
317 | (cdr args))) | |
318 | ;; Move on to optional arguments. | |
319 | (if (not kw) | |
320 | ;; Without keywords, bind optionals from arguments. | |
321 | (let lp ((env env) | |
322 | (nopt nopt) | |
323 | (args args) | |
324 | (inits inits)) | |
325 | (if (zero? nopt) | |
326 | (if rest? | |
327 | (eval body (cons args env)) | |
328 | (if (null? args) | |
329 | (eval body env) | |
330 | (if alt | |
331 | (apply alt-proc %args) | |
332 | (scm-error 'wrong-number-of-args | |
333 | "eval" "Wrong number of arguments" | |
334 | '() #f)))) | |
335 | (if (null? args) | |
336 | (lp (cons (eval (car inits) env) env) | |
337 | (1- nopt) args (cdr inits)) | |
338 | (lp (cons (car args) env) | |
339 | (1- nopt) (cdr args) (cdr inits))))) | |
f3cf9421 AW |
340 | (let lp ((env env) |
341 | (nopt* nopt) | |
342 | (args args) | |
343 | (inits inits)) | |
581f410f AW |
344 | (cond |
345 | ;; With keywords, we stop binding optionals at the | |
346 | ;; first keyword. | |
347 | ((> nopt* 0) | |
348 | (if (or (null? args) (keyword? (car args))) | |
349 | (lp (cons (eval (car inits) env) env) | |
350 | (1- nopt*) args (cdr inits)) | |
351 | (lp (cons (car args) env) | |
352 | (1- nopt*) (cdr args) (cdr inits)))) | |
353 | ;; Finished with optionals. | |
354 | ((and alt (pair? args) (not (keyword? (car args))) | |
355 | (not rest?)) | |
356 | ;; Too many positional args, no #:rest arg, | |
357 | ;; and we have an alternate. | |
358 | (apply alt-proc %args)) | |
359 | (else | |
360 | (let* ((aok (car kw)) | |
361 | (kw (cdr kw)) | |
362 | (kw-base (+ nopt nreq (if rest? 1 0))) | |
363 | (imax (let lp ((imax (1- kw-base)) (kw kw)) | |
364 | (if (null? kw) | |
365 | imax | |
366 | (lp (max (cdar kw) imax) | |
367 | (cdr kw))))) | |
368 | ;; Fill in kwargs with "undefined" vals. | |
369 | (env (let lp ((i kw-base) | |
370 | ;; Also, here we bind the rest | |
371 | ;; arg, if any. | |
372 | (env (if rest? | |
373 | (cons args env) | |
374 | env))) | |
375 | (if (<= i imax) | |
376 | (lp (1+ i) (cons unbound-arg env)) | |
377 | env)))) | |
378 | ;; Now scan args for keywords. | |
379 | (let lp ((args args)) | |
380 | (if (and (pair? args) (pair? (cdr args)) | |
381 | (keyword? (car args))) | |
382 | (let ((kw-pair (assq (car args) kw)) | |
383 | (v (cadr args))) | |
384 | (if kw-pair | |
385 | ;; Found a known keyword; set its value. | |
386 | (list-set! env | |
387 | (- imax (cdr kw-pair)) v) | |
388 | ;; Unknown keyword. | |
389 | (if (not aok) | |
390 | (scm-error | |
391 | 'keyword-argument-error | |
392 | "eval" "Unrecognized keyword" | |
4af0d97e | 393 | '() (list (car args))))) |
581f410f AW |
394 | (lp (cddr args))) |
395 | (if (pair? args) | |
396 | (if rest? | |
397 | ;; Be lenient parsing rest args. | |
398 | (lp (cdr args)) | |
399 | (scm-error 'keyword-argument-error | |
400 | "eval" "Invalid keyword" | |
4af0d97e | 401 | '() (list (car args)))) |
581f410f AW |
402 | ;; Finished parsing keywords. Fill in |
403 | ;; uninitialized kwargs by evalling init | |
404 | ;; expressions in their appropriate | |
405 | ;; environment. | |
406 | (let lp ((i (- imax kw-base)) | |
407 | (inits inits)) | |
408 | (if (pair? inits) | |
409 | (let ((tail (list-tail env i))) | |
410 | (if (eq? (car tail) unbound-arg) | |
411 | (set-car! tail | |
412 | (eval (car inits) | |
413 | (cdr tail)))) | |
414 | (lp (1- i) (cdr inits))) | |
415 | ;; Finally, eval the body. | |
416 | (eval body env)))))))))))))))) | |
d8a071fc | 417 | |
b2b554ef | 418 | ;; The "engine". EXP is a memoized expression. |
5161a3c0 AW |
419 | (define (eval exp env) |
420 | (memoized-expression-case exp | |
21ec0bd9 | 421 | (('lexical-ref n) |
bb0c8157 AW |
422 | (list-ref env n)) |
423 | ||
21ec0bd9 AW |
424 | (('call (f nargs . args)) |
425 | (let ((proc (eval f env))) | |
426 | (call eval proc nargs args env))) | |
427 | ||
428 | (('toplevel-ref var-or-sym) | |
429 | (variable-ref | |
430 | (if (variable? var-or-sym) | |
431 | var-or-sym | |
bb0c8157 AW |
432 | (memoize-variable-access! exp |
433 | (capture-env (if (pair? env) | |
434 | (cdr (last-pair env)) | |
435 | env)))))) | |
21ec0bd9 | 436 | |
5161a3c0 AW |
437 | (('if (test consequent . alternate)) |
438 | (if (eval test env) | |
439 | (eval consequent env) | |
440 | (eval alternate env))) | |
441 | ||
21ec0bd9 AW |
442 | (('quote x) |
443 | x) | |
444 | ||
5161a3c0 AW |
445 | (('let (inits . body)) |
446 | (let lp ((inits inits) (new-env (capture-env env))) | |
447 | (if (null? inits) | |
448 | (eval body new-env) | |
449 | (lp (cdr inits) | |
450 | (cons (eval (car inits) env) new-env))))) | |
c438cd71 LC |
451 | |
452 | (('lambda (body docstring nreq . tail)) | |
453 | (let ((proc | |
454 | (if (null? tail) | |
455 | (make-fixed-closure eval nreq body (capture-env env)) | |
456 | (if (null? (cdr tail)) | |
a4b64fa2 | 457 | (make-rest-closure eval nreq body (capture-env env)) |
c438cd71 LC |
458 | (apply make-general-closure (capture-env env) |
459 | body nreq tail))))) | |
460 | (when docstring | |
461 | (set-procedure-property! proc 'documentation docstring)) | |
462 | proc)) | |
d8a071fc | 463 | |
6fc3eae4 AW |
464 | (('seq (head . tail)) |
465 | (begin | |
466 | (eval head env) | |
467 | (eval tail env))) | |
468 | ||
5161a3c0 AW |
469 | (('lexical-set! (n . x)) |
470 | (let ((val (eval x env))) | |
bb0c8157 | 471 | (list-set! env n val))) |
5161a3c0 | 472 | |
21ec0bd9 AW |
473 | (('call-with-values (producer . consumer)) |
474 | (call-with-values (eval producer env) | |
475 | (eval consumer env))) | |
476 | ||
477 | (('apply (f args)) | |
478 | (apply (eval f env) (eval args env))) | |
479 | ||
480 | (('module-ref var-or-spec) | |
5161a3c0 | 481 | (variable-ref |
21ec0bd9 AW |
482 | (if (variable? var-or-spec) |
483 | var-or-spec | |
484 | (memoize-variable-access! exp #f)))) | |
5161a3c0 | 485 | |
21ec0bd9 | 486 | (('define (name . x)) |
ee15aa46 AW |
487 | (let ((x (eval x env))) |
488 | (if (and (procedure? x) (not (procedure-property x 'name))) | |
489 | (set-procedure-property! x 'name name)) | |
adb8054c MW |
490 | (define! name x) |
491 | (if #f #f))) | |
21ec0bd9 | 492 | |
5161a3c0 AW |
493 | (('toplevel-set! (var-or-sym . x)) |
494 | (variable-set! | |
495 | (if (variable? var-or-sym) | |
496 | var-or-sym | |
bb0c8157 AW |
497 | (memoize-variable-access! exp |
498 | (capture-env (if (pair? env) | |
499 | (cdr (last-pair env)) | |
500 | env)))) | |
5161a3c0 AW |
501 | (eval x env))) |
502 | ||
1773bc7d AW |
503 | (('call-with-prompt (tag thunk . handler)) |
504 | (call-with-prompt | |
505 | (eval tag env) | |
506 | (eval thunk env) | |
507 | (eval handler env))) | |
747022e4 | 508 | |
21ec0bd9 AW |
509 | (('call/cc proc) |
510 | (call/cc (eval proc env))) | |
5161a3c0 AW |
511 | |
512 | (('module-set! (x . var-or-spec)) | |
513 | (variable-set! | |
514 | (if (variable? var-or-spec) | |
515 | var-or-spec | |
516 | (memoize-variable-access! exp #f)) | |
517 | (eval x env))))) | |
518 | ||
b2b554ef | 519 | ;; primitive-eval |
5161a3c0 | 520 | (lambda (exp) |
b2b554ef | 521 | "Evaluate @var{exp} in the current module." |
5161a3c0 | 522 | (eval |
a310a1d1 AW |
523 | (memoize-expression |
524 | (if (macroexpanded? exp) | |
525 | exp | |
526 | ((module-transformer (current-module)) exp))) | |
5161a3c0 | 527 | '())))) |