Commit | Line | Data |
---|---|---|
5161a3c0 AW |
1 | ;;; -*- mode: scheme; coding: utf-8; -*- |
2 | ||
c438cd71 | 3 | ;;;; Copyright (C) 2009, 2010, 2012 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 | ||
9331f91c AW |
105 | (define-syntax call |
106 | (lambda (x) | |
107 | (define *max-static-call-count* 4) | |
108 | (syntax-case x () | |
109 | ((_ eval proc nargs args env) (identifier? #'env) | |
110 | #`(case nargs | |
111 | #,@(map (lambda (nargs) | |
112 | #`((#,nargs) | |
113 | (proc | |
114 | #,@(map | |
115 | (lambda (n) | |
116 | (let lp ((n n) (args #'args)) | |
117 | (if (zero? n) | |
118 | #`(eval (car #,args) env) | |
119 | (lp (1- n) #`(cdr #,args))))) | |
120 | (iota nargs))))) | |
121 | (iota *max-static-call-count*)) | |
122 | (else | |
123 | (apply proc | |
124 | #,@(map | |
125 | (lambda (n) | |
126 | (let lp ((n n) (args #'args)) | |
127 | (if (zero? n) | |
128 | #`(eval (car #,args) env) | |
129 | (lp (1- n) #`(cdr #,args))))) | |
130 | (iota *max-static-call-count*)) | |
131 | (let lp ((exps #,(let lp ((n *max-static-call-count*) | |
132 | (args #'args)) | |
133 | (if (zero? n) | |
134 | args | |
135 | (lp (1- n) #`(cdr #,args))))) | |
136 | (args '())) | |
137 | (if (null? exps) | |
138 | (reverse args) | |
139 | (lp (cdr exps) | |
140 | (cons (eval (car exps) env) args))))))))))) | |
141 | ||
b2b554ef AW |
142 | ;; This macro could be more straightforward if the compiler had better |
143 | ;; copy propagation. As it is we do some copy propagation by hand. | |
5161a3c0 AW |
144 | (define-syntax mx-bind |
145 | (lambda (x) | |
146 | (syntax-case x () | |
147 | ((_ data () body) | |
148 | #'body) | |
149 | ((_ data (a . b) body) (and (identifier? #'a) (identifier? #'b)) | |
150 | #'(let ((a (car data)) | |
151 | (b (cdr data))) | |
152 | body)) | |
153 | ((_ data (a . b) body) (identifier? #'a) | |
154 | #'(let ((a (car data)) | |
155 | (xb (cdr data))) | |
156 | (mx-bind xb b body))) | |
157 | ((_ data (a . b) body) | |
158 | #'(let ((xa (car data)) | |
159 | (xb (cdr data))) | |
160 | (mx-bind xa a (mx-bind xb b body)))) | |
161 | ((_ data v body) (identifier? #'v) | |
162 | #'(let ((v data)) | |
163 | body))))) | |
164 | ||
b2b554ef AW |
165 | ;; The resulting nested if statements will be an O(n) dispatch. Once |
166 | ;; we compile `case' effectively, this situation will improve. | |
5161a3c0 AW |
167 | (define-syntax mx-match |
168 | (lambda (x) | |
169 | (syntax-case x (quote) | |
170 | ((_ mx data tag) | |
171 | #'(error "what" mx)) | |
172 | ((_ mx data tag (('type pat) body) c* ...) | |
173 | #`(if (eqv? tag #,(or (memoized-typecode (syntax->datum #'type)) | |
174 | (error "not a typecode" #'type))) | |
175 | (mx-bind data pat body) | |
176 | (mx-match mx data tag c* ...)))))) | |
177 | ||
178 | (define-syntax memoized-expression-case | |
179 | (lambda (x) | |
180 | (syntax-case x () | |
181 | ((_ mx c ...) | |
182 | #'(let ((tag (memoized-expression-typecode mx)) | |
183 | (data (memoized-expression-data mx))) | |
184 | (mx-match mx data tag c ...))))))) | |
185 | ||
186 | ||
21ec0bd9 AW |
187 | ;;; |
188 | ;;; On 18 Feb 2010, I did a profile of how often the various memoized expression | |
189 | ;;; types occur when getting to a prompt on a fresh build. Here are the numbers | |
190 | ;;; I got: | |
191 | ;;; | |
192 | ;;; lexical-ref: 32933054 | |
193 | ;;; call: 20281547 | |
194 | ;;; toplevel-ref: 13228724 | |
195 | ;;; if: 9156156 | |
196 | ;;; quote: 6610137 | |
197 | ;;; let: 2619707 | |
198 | ;;; lambda: 1010921 | |
199 | ;;; begin: 948945 | |
200 | ;;; lexical-set: 509862 | |
201 | ;;; call-with-values: 139668 | |
202 | ;;; apply: 49402 | |
203 | ;;; module-ref: 14468 | |
204 | ;;; define: 1259 | |
205 | ;;; toplevel-set: 328 | |
206 | ;;; dynwind: 162 | |
207 | ;;; with-fluids: 0 | |
208 | ;;; call/cc: 0 | |
209 | ;;; module-set: 0 | |
210 | ;;; | |
211 | ;;; So until we compile `case' into a computed goto, we'll order the clauses in | |
212 | ;;; `eval' in this order, to put the most frequent cases first. | |
213 | ;;; | |
214 | ||
5161a3c0 AW |
215 | (define primitive-eval |
216 | (let () | |
d8a071fc AW |
217 | ;; We pre-generate procedures with fixed arities, up to some number of |
218 | ;; arguments; see make-fixed-closure above. | |
219 | ||
220 | ;; A unique marker for unbound keywords. | |
221 | (define unbound-arg (list 'unbound-arg)) | |
222 | ||
7572ee52 AW |
223 | ;; Procedures with rest, optional, or keyword arguments, potentially with |
224 | ;; multiple arities, as with case-lambda. | |
d8a071fc | 225 | (define (make-general-closure env body nreq rest? nopt kw inits alt) |
7572ee52 | 226 | (define alt-proc |
c438cd71 | 227 | (and alt ; (body docstring nreq ...) |
dc3e203e | 228 | (let* ((body (car alt)) |
c438cd71 LC |
229 | (spec (cddr alt)) |
230 | (nreq (car spec)) | |
231 | (rest (if (null? (cdr spec)) #f (cadr spec))) | |
232 | (tail (and (pair? (cdr spec)) (pair? (cddr spec)) (cddr spec))) | |
dc3e203e AW |
233 | (nopt (if tail (car tail) 0)) |
234 | (kw (and tail (cadr tail))) | |
235 | (inits (if tail (caddr tail) '())) | |
236 | (alt (and tail (cadddr tail)))) | |
237 | (make-general-closure env body nreq rest nopt kw inits alt)))) | |
f3cf9421 AW |
238 | (define (set-procedure-arity! proc) |
239 | (let lp ((alt alt) (nreq nreq) (nopt nopt) (rest? rest?)) | |
240 | (if (not alt) | |
fc835b1b AW |
241 | (begin |
242 | (set-procedure-property! proc 'arglist | |
243 | (list nreq | |
244 | nopt | |
245 | (if kw (cdr kw) '()) | |
246 | (and kw (car kw)) | |
247 | (and rest? '_))) | |
248 | (set-procedure-minimum-arity! proc nreq nopt rest?)) | |
c438cd71 LC |
249 | (let* ((spec (cddr alt)) |
250 | (nreq* (car spec)) | |
251 | (rest?* (if (null? (cdr spec)) #f (cadr spec))) | |
252 | (tail (and (pair? (cdr spec)) (pair? (cddr spec)) (cddr spec))) | |
f3cf9421 AW |
253 | (nopt* (if tail (car tail) 0)) |
254 | (alt* (and tail (cadddr tail)))) | |
255 | (if (or (< nreq* nreq) | |
256 | (and (= nreq* nreq) | |
257 | (if rest? | |
258 | (and rest?* (> nopt* nopt)) | |
259 | (or rest?* (> nopt* nopt))))) | |
260 | (lp alt* nreq* nopt* rest?*) | |
261 | (lp alt* nreq nopt rest?))))) | |
262 | proc) | |
263 | (set-procedure-arity! | |
264 | (lambda %args | |
265 | (let lp ((env env) | |
266 | (nreq* nreq) | |
267 | (args %args)) | |
268 | (if (> nreq* 0) | |
269 | ;; First, bind required arguments. | |
270 | (if (null? args) | |
271 | (if alt | |
272 | (apply alt-proc %args) | |
273 | (scm-error 'wrong-number-of-args | |
274 | "eval" "Wrong number of arguments" | |
275 | '() #f)) | |
276 | (lp (cons (car args) env) | |
277 | (1- nreq*) | |
278 | (cdr args))) | |
279 | ;; Move on to optional arguments. | |
280 | (if (not kw) | |
281 | ;; Without keywords, bind optionals from arguments. | |
282 | (let lp ((env env) | |
283 | (nopt nopt) | |
284 | (args args) | |
285 | (inits inits)) | |
286 | (if (zero? nopt) | |
287 | (if rest? | |
288 | (eval body (cons args env)) | |
289 | (if (null? args) | |
290 | (eval body env) | |
291 | (if alt | |
292 | (apply alt-proc %args) | |
293 | (scm-error 'wrong-number-of-args | |
294 | "eval" "Wrong number of arguments" | |
295 | '() #f)))) | |
296 | (if (null? args) | |
297 | (lp (cons (eval (car inits) env) env) | |
298 | (1- nopt) args (cdr inits)) | |
299 | (lp (cons (car args) env) | |
300 | (1- nopt) (cdr args) (cdr inits))))) | |
301 | ;; With keywords, we stop binding optionals at the first | |
302 | ;; keyword. | |
303 | (let lp ((env env) | |
304 | (nopt* nopt) | |
305 | (args args) | |
306 | (inits inits)) | |
307 | (if (> nopt* 0) | |
308 | (if (or (null? args) (keyword? (car args))) | |
309 | (lp (cons (eval (car inits) env) env) | |
310 | (1- nopt*) args (cdr inits)) | |
311 | (lp (cons (car args) env) | |
312 | (1- nopt*) (cdr args) (cdr inits))) | |
313 | ;; Finished with optionals. | |
314 | (let* ((aok (car kw)) | |
315 | (kw (cdr kw)) | |
316 | (kw-base (+ nopt nreq (if rest? 1 0))) | |
317 | (imax (let lp ((imax (1- kw-base)) (kw kw)) | |
318 | (if (null? kw) | |
319 | imax | |
320 | (lp (max (cdar kw) imax) | |
321 | (cdr kw))))) | |
322 | ;; Fill in kwargs with "undefined" vals. | |
323 | (env (let lp ((i kw-base) | |
324 | ;; Also, here we bind the rest | |
325 | ;; arg, if any. | |
326 | (env (if rest? (cons args env) env))) | |
327 | (if (<= i imax) | |
328 | (lp (1+ i) (cons unbound-arg env)) | |
329 | env)))) | |
330 | ;; Now scan args for keywords. | |
331 | (let lp ((args args)) | |
332 | (if (and (pair? args) (pair? (cdr args)) | |
333 | (keyword? (car args))) | |
334 | (let ((kw-pair (assq (car args) kw)) | |
335 | (v (cadr args))) | |
336 | (if kw-pair | |
337 | ;; Found a known keyword; set its value. | |
338 | (list-set! env (- imax (cdr kw-pair)) v) | |
339 | ;; Unknown keyword. | |
340 | (if (not aok) | |
341 | (scm-error 'keyword-argument-error | |
342 | "eval" "Unrecognized keyword" | |
343 | '() #f))) | |
344 | (lp (cddr args))) | |
345 | (if (pair? args) | |
346 | (if rest? | |
347 | ;; Be lenient parsing rest args. | |
348 | (lp (cdr args)) | |
349 | (scm-error 'keyword-argument-error | |
350 | "eval" "Invalid keyword" | |
351 | '() #f)) | |
352 | ;; Finished parsing keywords. Fill in | |
353 | ;; uninitialized kwargs by evalling init | |
354 | ;; expressions in their appropriate | |
355 | ;; environment. | |
356 | (let lp ((i (- imax kw-base)) | |
357 | (inits inits)) | |
358 | (if (pair? inits) | |
359 | (let ((tail (list-tail env i))) | |
360 | (if (eq? (car tail) unbound-arg) | |
361 | (set-car! tail | |
362 | (eval (car inits) | |
363 | (cdr tail)))) | |
364 | (lp (1- i) (cdr inits))) | |
365 | ;; Finally, eval the body. | |
366 | (eval body env))))))))))))))) | |
d8a071fc | 367 | |
b2b554ef | 368 | ;; The "engine". EXP is a memoized expression. |
5161a3c0 AW |
369 | (define (eval exp env) |
370 | (memoized-expression-case exp | |
21ec0bd9 | 371 | (('lexical-ref n) |
bb0c8157 AW |
372 | (list-ref env n)) |
373 | ||
21ec0bd9 AW |
374 | (('call (f nargs . args)) |
375 | (let ((proc (eval f env))) | |
376 | (call eval proc nargs args env))) | |
377 | ||
378 | (('toplevel-ref var-or-sym) | |
379 | (variable-ref | |
380 | (if (variable? var-or-sym) | |
381 | var-or-sym | |
bb0c8157 AW |
382 | (memoize-variable-access! exp |
383 | (capture-env (if (pair? env) | |
384 | (cdr (last-pair env)) | |
385 | env)))))) | |
21ec0bd9 | 386 | |
5161a3c0 AW |
387 | (('if (test consequent . alternate)) |
388 | (if (eval test env) | |
389 | (eval consequent env) | |
390 | (eval alternate env))) | |
391 | ||
21ec0bd9 AW |
392 | (('quote x) |
393 | x) | |
394 | ||
5161a3c0 AW |
395 | (('let (inits . body)) |
396 | (let lp ((inits inits) (new-env (capture-env env))) | |
397 | (if (null? inits) | |
398 | (eval body new-env) | |
399 | (lp (cdr inits) | |
400 | (cons (eval (car inits) env) new-env))))) | |
c438cd71 LC |
401 | |
402 | (('lambda (body docstring nreq . tail)) | |
403 | (let ((proc | |
404 | (if (null? tail) | |
405 | (make-fixed-closure eval nreq body (capture-env env)) | |
406 | (if (null? (cdr tail)) | |
407 | (make-general-closure (capture-env env) body | |
408 | nreq (car tail) | |
409 | 0 #f '() #f) | |
410 | (apply make-general-closure (capture-env env) | |
411 | body nreq tail))))) | |
412 | (when docstring | |
413 | (set-procedure-property! proc 'documentation docstring)) | |
414 | proc)) | |
d8a071fc | 415 | |
21ec0bd9 AW |
416 | (('begin (first . rest)) |
417 | (let lp ((first first) (rest rest)) | |
418 | (if (null? rest) | |
419 | (eval first env) | |
420 | (begin | |
421 | (eval first env) | |
422 | (lp (car rest) (cdr rest)))))) | |
5161a3c0 AW |
423 | |
424 | (('lexical-set! (n . x)) | |
425 | (let ((val (eval x env))) | |
bb0c8157 | 426 | (list-set! env n val))) |
5161a3c0 | 427 | |
21ec0bd9 AW |
428 | (('call-with-values (producer . consumer)) |
429 | (call-with-values (eval producer env) | |
430 | (eval consumer env))) | |
431 | ||
432 | (('apply (f args)) | |
433 | (apply (eval f env) (eval args env))) | |
434 | ||
435 | (('module-ref var-or-spec) | |
5161a3c0 | 436 | (variable-ref |
21ec0bd9 AW |
437 | (if (variable? var-or-spec) |
438 | var-or-spec | |
439 | (memoize-variable-access! exp #f)))) | |
5161a3c0 | 440 | |
21ec0bd9 | 441 | (('define (name . x)) |
ee15aa46 AW |
442 | (let ((x (eval x env))) |
443 | (if (and (procedure? x) (not (procedure-property x 'name))) | |
444 | (set-procedure-property! x 'name name)) | |
adb8054c MW |
445 | (define! name x) |
446 | (if #f #f))) | |
21ec0bd9 | 447 | |
5161a3c0 AW |
448 | (('toplevel-set! (var-or-sym . x)) |
449 | (variable-set! | |
450 | (if (variable? var-or-sym) | |
451 | var-or-sym | |
bb0c8157 AW |
452 | (memoize-variable-access! exp |
453 | (capture-env (if (pair? env) | |
454 | (cdr (last-pair env)) | |
455 | env)))) | |
5161a3c0 AW |
456 | (eval x env))) |
457 | ||
21ec0bd9 AW |
458 | (('dynwind (in exp . out)) |
459 | (dynamic-wind (eval in env) | |
460 | (lambda () (eval exp env)) | |
461 | (eval out env))) | |
462 | ||
bb0229b5 AW |
463 | (('with-fluids (fluids vals . exp)) |
464 | (let* ((fluids (map (lambda (x) (eval x env)) fluids)) | |
465 | (vals (map (lambda (x) (eval x env)) vals))) | |
1371fe9b AW |
466 | (let lp ((fluids fluids) (vals vals)) |
467 | (if (null? fluids) | |
468 | (eval exp env) | |
469 | (with-fluids (((car fluids) (car vals))) | |
470 | (lp (cdr fluids) (cdr vals))))))) | |
bb0229b5 | 471 | |
747022e4 AW |
472 | (('prompt (tag exp . handler)) |
473 | (@prompt (eval tag env) | |
474 | (eval exp env) | |
475 | (eval handler env))) | |
476 | ||
21ec0bd9 AW |
477 | (('call/cc proc) |
478 | (call/cc (eval proc env))) | |
5161a3c0 AW |
479 | |
480 | (('module-set! (x . var-or-spec)) | |
481 | (variable-set! | |
482 | (if (variable? var-or-spec) | |
483 | var-or-spec | |
484 | (memoize-variable-access! exp #f)) | |
485 | (eval x env))))) | |
486 | ||
b2b554ef | 487 | ;; primitive-eval |
5161a3c0 | 488 | (lambda (exp) |
b2b554ef | 489 | "Evaluate @var{exp} in the current module." |
5161a3c0 | 490 | (eval |
a310a1d1 AW |
491 | (memoize-expression |
492 | (if (macroexpanded? exp) | |
493 | exp | |
494 | ((module-transformer (current-module)) exp))) | |
5161a3c0 | 495 | '())))) |