1 ;;; -*- mode: scheme; coding: utf-8; -*-
3 ;;;; Copyright (C) 2009, 2010, 2011
4 ;;;; Free Software Foundation, Inc.
6 ;;;; This library is free software; you can redistribute it and/or
7 ;;;; modify it under the terms of the GNU Lesser General Public
8 ;;;; License as published by the Free Software Foundation; either
9 ;;;; version 3 of the License, or (at your option) any later version.
11 ;;;; This library is distributed in the hope that it will be useful,
12 ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
13 ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 ;;;; Lesser General Public License for more details.
16 ;;;; You should have received a copy of the GNU Lesser General Public
17 ;;;; License along with this library; if not, write to the Free Software
18 ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 ;;; Scheme eval, written in Scheme.
27 ;;; Expressions are first expanded, by the syntax expander (i.e.
28 ;;; psyntax), then memoized into internal forms. The evaluator itself
29 ;;; only operates on the internal forms ("memoized expressions").
31 ;;; Environments are represented as linked lists of the form (VAL ... .
32 ;;; MOD). If MOD is #f, it means the environment was captured before
33 ;;; modules were booted. If MOD is the literal value '(), we are
34 ;;; evaluating at the top level, and so should track changes to the
37 ;;; Evaluate this in Emacs to make code indentation work right:
39 ;;; (put 'memoized-expression-case 'scheme-indent-function 1)
47 (define-syntax capture-env
50 (let ((env (exp ...)))
56 ;; the and current-module checks that modules are booted,
57 ;; and thus the-root-module is defined
58 (and (current-module) the-root-module)
61 ;; Fast case for procedures with fixed arities.
62 (define-syntax make-fixed-closure
64 (define *max-static-argument-count* 8)
65 (define (make-formals n)
70 (string (integer->char (+ (char->integer #\a) i))))))
73 ((_ eval nreq body env) (not (identifier? #'env))
75 (make-fixed-closure eval nreq body e)))
76 ((_ eval nreq body env)
78 #,@(map (lambda (nreq)
79 (let ((formals (make-formals nreq)))
83 (cons* #,@(reverse formals) env))))))
84 (iota *max-static-argument-count*))
86 #,(let ((formals (make-formals *max-static-argument-count*)))
87 #`(lambda (#,@formals . more)
88 (let lp ((new-env (cons* #,@(reverse formals) env))
89 (nreq (- nreq #,*max-static-argument-count*))
95 (scm-error 'wrong-number-of-args
96 "eval" "Wrong number of arguments"
99 (scm-error 'wrong-number-of-args
100 "eval" "Wrong number of arguments"
102 (lp (cons (car args) new-env)
104 (cdr args)))))))))))))
108 (define *max-static-call-count* 4)
110 ((_ eval proc nargs args env) (identifier? #'env)
112 #,@(map (lambda (nargs)
117 (let lp ((n n) (args #'args))
119 #`(eval (car #,args) env)
120 (lp (1- n) #`(cdr #,args)))))
122 (iota *max-static-call-count*))
127 (let lp ((n n) (args #'args))
129 #`(eval (car #,args) env)
130 (lp (1- n) #`(cdr #,args)))))
131 (iota *max-static-call-count*))
132 (let lp ((exps #,(let lp ((n *max-static-call-count*)
136 (lp (1- n) #`(cdr #,args)))))
141 (cons (eval (car exps) env) args)))))))))))
143 ;; This macro could be more straightforward if the compiler had better
144 ;; copy propagation. As it is we do some copy propagation by hand.
145 (define-syntax mx-bind
150 ((_ data (a . b) body) (and (identifier? #'a) (identifier? #'b))
151 #'(let ((a (car data))
154 ((_ data (a . b) body) (identifier? #'a)
155 #'(let ((a (car data))
157 (mx-bind xb b body)))
158 ((_ data (a . b) body)
159 #'(let ((xa (car data))
161 (mx-bind xa a (mx-bind xb b body))))
162 ((_ data v body) (identifier? #'v)
166 ;; The resulting nested if statements will be an O(n) dispatch. Once
167 ;; we compile `case' effectively, this situation will improve.
168 (define-syntax mx-match
170 (syntax-case x (quote)
173 ((_ mx data tag (('type pat) body) c* ...)
174 #`(if (eqv? tag #,(or (memoized-typecode (syntax->datum #'type))
175 (error "not a typecode" #'type)))
176 (mx-bind data pat body)
177 (mx-match mx data tag c* ...))))))
179 (define-syntax memoized-expression-case
183 #'(let ((tag (memoized-expression-typecode mx))
184 (data (memoized-expression-data mx)))
185 (mx-match mx data tag c ...)))))))
189 ;;; On 18 Feb 2010, I did a profile of how often the various memoized expression
190 ;;; types occur when getting to a prompt on a fresh build. Here are the numbers
193 ;;; lexical-ref: 32933054
195 ;;; toplevel-ref: 13228724
201 ;;; lexical-set: 509862
202 ;;; call-with-values: 139668
204 ;;; module-ref: 14468
206 ;;; toplevel-set: 328
212 ;;; So until we compile `case' into a computed goto, we'll order the clauses in
213 ;;; `eval' in this order, to put the most frequent cases first.
216 (define primitive-eval
218 ;; We pre-generate procedures with fixed arities, up to some number of
219 ;; arguments; see make-fixed-closure above.
221 ;; A unique marker for unbound keywords.
222 (define unbound-arg (list 'unbound-arg))
224 ;; Procedures with rest, optional, or keyword arguments, potentially with
225 ;; multiple arities, as with case-lambda.
226 (define (make-general-closure env body nreq rest? nopt kw inits alt)
229 (let* ((body (car alt))
231 (rest (if (null? (cddr alt)) #f (caddr alt)))
232 (tail (and (pair? (cddr alt)) (pair? (cdddr alt)) (cdddr alt)))
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))))
238 (define (set-procedure-arity! proc)
239 (let lp ((alt alt) (nreq nreq) (nopt nopt) (rest? rest?))
242 (set-procedure-property! proc 'arglist
248 (set-procedure-minimum-arity! proc nreq nopt rest?))
249 (let* ((nreq* (cadr alt))
250 (rest?* (if (null? (cddr alt)) #f (caddr alt)))
251 (tail (and (pair? (cddr alt)) (pair? (cdddr alt)) (cdddr alt)))
252 (nopt* (if tail (car tail) 0))
253 (alt* (and tail (cadddr tail))))
254 (if (or (< nreq* nreq)
257 (and rest?* (> nopt* nopt))
258 (or rest?* (> nopt* nopt)))))
259 (lp alt* nreq* nopt* rest?*)
260 (lp alt* nreq nopt rest?)))))
262 (set-procedure-arity!
268 ;; First, bind required arguments.
271 (apply alt-proc %args)
272 (scm-error 'wrong-number-of-args
273 "eval" "Wrong number of arguments"
275 (lp (cons (car args) env)
278 ;; Move on to optional arguments.
280 ;; Without keywords, bind optionals from arguments.
287 (eval body (cons args env))
291 (apply alt-proc %args)
292 (scm-error 'wrong-number-of-args
293 "eval" "Wrong number of arguments"
296 (lp (cons (eval (car inits) env) env)
297 (1- nopt) args (cdr inits))
298 (lp (cons (car args) env)
299 (1- nopt) (cdr args) (cdr inits)))))
300 ;; With keywords, we stop binding optionals at the first
307 (if (or (null? args) (keyword? (car args)))
308 (lp (cons (eval (car inits) env) env)
309 (1- nopt*) args (cdr inits))
310 (lp (cons (car args) env)
311 (1- nopt*) (cdr args) (cdr inits)))
312 ;; Finished with optionals.
313 (let* ((aok (car kw))
315 (kw-base (+ nopt nreq (if rest? 1 0)))
316 (imax (let lp ((imax (1- kw-base)) (kw kw))
319 (lp (max (cdar kw) imax)
321 ;; Fill in kwargs with "undefined" vals.
322 (env (let lp ((i kw-base)
323 ;; Also, here we bind the rest
325 (env (if rest? (cons args env) env)))
327 (lp (1+ i) (cons unbound-arg env))
329 ;; Now scan args for keywords.
330 (let lp ((args args))
331 (if (and (pair? args) (pair? (cdr args))
332 (keyword? (car args)))
333 (let ((kw-pair (assq (car args) kw))
336 ;; Found a known keyword; set its value.
337 (list-set! env (- imax (cdr kw-pair)) v)
340 (scm-error 'keyword-argument-error
341 "eval" "Unrecognized keyword"
346 ;; Be lenient parsing rest args.
348 (scm-error 'keyword-argument-error
349 "eval" "Invalid keyword"
351 ;; Finished parsing keywords. Fill in
352 ;; uninitialized kwargs by evalling init
353 ;; expressions in their appropriate
355 (let lp ((i (- imax kw-base))
358 (let ((tail (list-tail env i)))
359 (if (eq? (car tail) unbound-arg)
363 (lp (1- i) (cdr inits)))
364 ;; Finally, eval the body.
365 (eval body env)))))))))))))))
367 ;; The "engine". EXP is a memoized expression.
368 (define (eval exp env)
369 (memoized-expression-case exp
373 (('call (f nargs . args))
374 (let ((proc (eval f env)))
375 (call eval proc nargs args env)))
377 (('toplevel-ref var-or-sym)
379 (if (variable? var-or-sym)
381 (memoize-variable-access! exp
382 (capture-env (if (pair? env)
383 (cdr (last-pair env))
386 (('if (test consequent . alternate))
388 (eval consequent env)
389 (eval alternate env)))
394 (('let (inits . body))
395 (let lp ((inits inits) (new-env (capture-env env)))
399 (cons (eval (car inits) env) new-env)))))
401 (('lambda (body nreq . tail))
403 (make-fixed-closure eval nreq body (capture-env env))
404 (if (null? (cdr tail))
405 (make-general-closure (capture-env env) body nreq (car tail)
407 (apply make-general-closure (capture-env env) body nreq tail))))
409 (('seq (head . tail))
414 (('lexical-set! (n . x))
415 (let ((val (eval x env)))
416 (list-set! env n val)))
418 (('call-with-values (producer . consumer))
419 (call-with-values (eval producer env)
420 (eval consumer env)))
423 (apply (eval f env) (eval args env)))
425 (('module-ref var-or-spec)
427 (if (variable? var-or-spec)
429 (memoize-variable-access! exp #f))))
431 (('define (name . x))
432 (let ((x (eval x env)))
433 (if (and (procedure? x) (not (procedure-property x 'name)))
434 (set-procedure-property! x 'name name))
438 (('toplevel-set! (var-or-sym . x))
440 (if (variable? var-or-sym)
442 (memoize-variable-access! exp
443 (capture-env (if (pair? env)
444 (cdr (last-pair env))
448 (('dynwind (in exp . out))
449 (dynamic-wind (eval in env)
450 (lambda () (eval exp env))
453 (('with-fluids (fluids vals . exp))
454 (let* ((fluids (map (lambda (x) (eval x env)) fluids))
455 (vals (map (lambda (x) (eval x env)) vals)))
456 (let lp ((fluids fluids) (vals vals))
459 (with-fluids (((car fluids) (car vals)))
460 (lp (cdr fluids) (cdr vals)))))))
462 (('prompt (tag exp . handler))
463 (@prompt (eval tag env)
468 (call/cc (eval proc env)))
470 (('module-set! (x . var-or-spec))
472 (if (variable? var-or-spec)
474 (memoize-variable-access! exp #f))
479 "Evaluate @var{exp} in the current module."
482 (if (macroexpanded? exp)
484 ((module-transformer (current-module)) exp)))