module/ice-9/eval.scm

   1 ;;; -*- mode: scheme; coding: utf-8; -*-
   2
   3 ;;;; Copyright (C) 2009, 2010, 2011
   4 ;;;; Free Software Foundation, Inc.
   5 ;;;;
   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.
  10 ;;;;
  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.
  15 ;;;;
  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
  19 ;;;;
  20
  21 \f
  22
  23 ;;; Commentary:
  24
  25 ;;; Scheme eval, written in Scheme.
  26 ;;;
  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").
  30 ;;;
  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
  35 ;;; current module.
  36 ;;;
  37 ;;; Evaluate this in Emacs to make code indentation work right:
  38 ;;;
  39 ;;;    (put 'memoized-expression-case 'scheme-indent-function 1)
  40 ;;;
  41
  42 ;;; Code:
  43
  44 \f
  45
  46 (eval-when (compile)
  47   (define-syntax capture-env
  48     (syntax-rules ()
  49       ((_ (exp ...))
  50        (let ((env (exp ...)))
  51          (capture-env env)))
  52       ((_ env)
  53        (if (null? env)
  54            (current-module)
  55            (if (not env)
  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)
  59                env)))))
  60
  61   ;; Fast case for procedures with fixed arities.
  62   (define-syntax make-fixed-closure
  63     (lambda (x)
  64       (define *max-static-argument-count* 8)
  65       (define (make-formals n)
  66         (map (lambda (i)
  67                (datum->syntax
  68                 x
  69                 (string->symbol
  70                  (string (integer->char (+ (char->integer #\a) i))))))
  71              (iota n)))
  72       (syntax-case x ()
  73         ((_ eval nreq body env) (not (identifier? #'env))
  74          #'(let ((e env))
  75              (make-fixed-closure eval nreq body e)))
  76         ((_ eval nreq body env)
  77          #`(case nreq
  78              #,@(map (lambda (nreq)
  79                        (let ((formals (make-formals nreq)))
  80                          #`((#,nreq)
  81                             (lambda (#,@formals)
  82                               (eval body
  83                                     (cons* #,@(reverse formals) env))))))
  84                      (iota *max-static-argument-count*))
  85              (else
  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*))
  90                                (args more))
  91                         (if (zero? nreq)
  92                             (eval body
  93                                   (if (null? args)
  94                                       new-env
  95                                       (scm-error 'wrong-number-of-args
  96                                                  "eval" "Wrong number of arguments"
  97                                                  '() #f)))
  98                             (if (null? args)
  99                                 (scm-error 'wrong-number-of-args
 100                                            "eval" "Wrong number of arguments"
 101                                            '() #f)
 102                                 (lp (cons (car args) new-env)
 103                                     (1- nreq)
 104                                     (cdr args)))))))))))))
 105
 106   (define-syntax call
 107     (lambda (x)
 108       (define *max-static-call-count* 4)
 109       (syntax-case x ()
 110         ((_ eval proc nargs args env) (identifier? #'env)
 111          #`(case nargs
 112              #,@(map (lambda (nargs)
 113                        #`((#,nargs)
 114                           (proc
 115                            #,@(map
 116                                (lambda (n)
 117                                  (let lp ((n n) (args #'args))
 118                                    (if (zero? n)
 119                                        #`(eval (car #,args) env)
 120                                        (lp (1- n) #`(cdr #,args)))))
 121                                (iota nargs)))))
 122                      (iota *max-static-call-count*))
 123              (else
 124               (apply proc
 125                      #,@(map
 126                          (lambda (n)
 127                            (let lp ((n n) (args #'args))
 128                              (if (zero? n)
 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*)
 133                                                (args #'args))
 134                                         (if (zero? n)
 135                                             args
 136                                             (lp (1- n) #`(cdr #,args)))))
 137                               (args '()))
 138                        (if (null? exps)
 139                            (reverse args)
 140                            (lp (cdr exps)
 141                                (cons (eval (car exps) env) args)))))))))))
 142
 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
 146     (lambda (x)
 147       (syntax-case x ()
 148         ((_ data () body)
 149          #'body)
 150         ((_ data (a . b) body) (and (identifier? #'a) (identifier? #'b))
 151          #'(let ((a (car data))
 152                  (b (cdr data)))
 153              body))
 154         ((_ data (a . b) body) (identifier? #'a)
 155          #'(let ((a (car data))
 156                  (xb (cdr data)))
 157              (mx-bind xb b body)))
 158         ((_ data (a . b) body)
 159          #'(let ((xa (car data))
 160                  (xb (cdr data)))
 161              (mx-bind xa a (mx-bind xb b body))))
 162         ((_ data v body) (identifier? #'v)
 163          #'(let ((v data))
 164              body)))))
 165
 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
 169     (lambda (x)
 170       (syntax-case x (quote)
 171         ((_ mx data tag)
 172          #'(error "what" mx))
 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* ...))))))
 178
 179   (define-syntax memoized-expression-case
 180     (lambda (x)
 181       (syntax-case x ()
 182         ((_ mx c ...)
 183          #'(let ((tag (memoized-expression-typecode mx))
 184                  (data (memoized-expression-data mx)))
 185              (mx-match mx data tag c ...)))))))
 186
 187
 188 ;;;
 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
 191 ;;; I got:
 192 ;;;
 193 ;;;      lexical-ref: 32933054
 194 ;;;             call: 20281547
 195 ;;;     toplevel-ref: 13228724
 196 ;;;               if: 9156156
 197 ;;;            quote: 6610137
 198 ;;;              let: 2619707
 199 ;;;           lambda: 1010921
 200 ;;;            begin: 948945
 201 ;;;      lexical-set: 509862
 202 ;;; call-with-values: 139668
 203 ;;;            apply: 49402
 204 ;;;       module-ref: 14468
 205 ;;;           define: 1259
 206 ;;;     toplevel-set: 328
 207 ;;;          dynwind: 162
 208 ;;;      with-fluids: 0
 209 ;;;          call/cc: 0
 210 ;;;       module-set: 0
 211 ;;;
 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.
 214 ;;;
 215
 216 (define primitive-eval
 217   (let ()
 218     ;; We pre-generate procedures with fixed arities, up to some number of
 219     ;; arguments; see make-fixed-closure above.
 220
 221     ;; A unique marker for unbound keywords.
 222     (define unbound-arg (list 'unbound-arg))
 223
 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)
 227       (define alt-proc
 228         (and alt
 229              (let* ((body (car alt))
 230                     (nreq (cadr 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?))
 240           (if (not alt)
 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?))
 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)
 255                         (and (= nreq* nreq)
 256                              (if rest?
 257                                  (and rest?* (> nopt* nopt))
 258                                  (or rest?* (> nopt* nopt)))))
 259                     (lp alt* nreq* nopt* rest?*)
 260                     (lp alt* nreq nopt rest?)))))
 261         proc)
 262       (set-procedure-arity!
 263        (lambda %args
 264          (let lp ((env env)
 265                   (nreq* nreq)
 266                   (args %args))
 267            (if (> nreq* 0)
 268                ;; First, bind required arguments.
 269                (if (null? args)
 270                    (if alt
 271                        (apply alt-proc %args)
 272                        (scm-error 'wrong-number-of-args
 273                                   "eval" "Wrong number of arguments"
 274                                   '() #f))
 275                    (lp (cons (car args) env)
 276                        (1- nreq*)
 277                        (cdr args)))
 278                ;; Move on to optional arguments.
 279                (if (not kw)
 280                    ;; Without keywords, bind optionals from arguments.
 281                    (let lp ((env env)
 282                             (nopt nopt)
 283                             (args args)
 284                             (inits inits))
 285                      (if (zero? nopt)
 286                          (if rest?
 287                              (eval body (cons args env))
 288                              (if (null? args)
 289                                  (eval body env)
 290                                  (if alt
 291                                      (apply alt-proc %args)
 292                                      (scm-error 'wrong-number-of-args
 293                                                 "eval" "Wrong number of arguments"
 294                                                 '() #f))))
 295                          (if (null? args)
 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
 301                    ;; keyword.
 302                    (let lp ((env env)
 303                             (nopt* nopt)
 304                             (args args)
 305                             (inits inits))
 306                      (if (> nopt* 0)
 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))
 314                                 (kw (cdr kw))
 315                                 (kw-base (+ nopt nreq (if rest? 1 0)))
 316                                 (imax (let lp ((imax (1- kw-base)) (kw kw))
 317                                         (if (null? kw)
 318                                             imax
 319                                             (lp (max (cdar kw) imax)
 320                                                 (cdr kw)))))
 321                                 ;; Fill in kwargs  with "undefined" vals.
 322                                 (env (let lp ((i kw-base)
 323                                               ;; Also, here we bind the rest
 324                                               ;; arg, if any.
 325                                               (env (if rest? (cons args env) env)))
 326                                        (if (<= i imax)
 327                                            (lp (1+ i) (cons unbound-arg env))
 328                                            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))
 334                                        (v (cadr args)))
 335                                    (if kw-pair
 336                                        ;; Found a known keyword; set its value.
 337                                        (list-set! env (- imax (cdr kw-pair)) v)
 338                                        ;; Unknown keyword.
 339                                        (if (not aok)
 340                                            (scm-error 'keyword-argument-error
 341                                                       "eval" "Unrecognized keyword"
 342                                                       '() #f)))
 343                                    (lp (cddr args)))
 344                                  (if (pair? args)
 345                                      (if rest?
 346                                          ;; Be lenient parsing rest args.
 347                                          (lp (cdr args))
 348                                          (scm-error 'keyword-argument-error
 349                                                     "eval" "Invalid keyword"
 350                                                     '() #f))
 351                                      ;; Finished parsing keywords. Fill in
 352                                      ;; uninitialized kwargs by evalling init
 353                                      ;; expressions in their appropriate
 354                                      ;; environment.
 355                                      (let lp ((i (- imax kw-base))
 356                                               (inits inits))
 357                                        (if (pair? inits)
 358                                            (let ((tail (list-tail env i)))
 359                                              (if (eq? (car tail) unbound-arg)
 360                                                  (set-car! tail
 361                                                            (eval (car inits)
 362                                                                  (cdr tail))))
 363                                              (lp (1- i) (cdr inits)))
 364                                            ;; Finally, eval the body.
 365                                            (eval body env)))))))))))))))
 366
 367     ;; The "engine". EXP is a memoized expression.
 368     (define (eval exp env)
 369       (memoized-expression-case exp
 370         (('lexical-ref n)
 371          (list-ref env n))
 372
 373         (('call (f nargs . args))
 374          (let ((proc (eval f env)))
 375            (call eval proc nargs args env)))
 376
 377         (('toplevel-ref var-or-sym)
 378          (variable-ref
 379           (if (variable? var-or-sym)
 380               var-or-sym
 381               (memoize-variable-access! exp
 382                                         (capture-env (if (pair? env)
 383                                                          (cdr (last-pair env))
 384                                                          env))))))
 385
 386         (('if (test consequent . alternate))
 387          (if (eval test env)
 388              (eval consequent env)
 389              (eval alternate env)))
 390
 391         (('quote x)
 392          x)
 393
 394         (('let (inits . body))
 395          (let lp ((inits inits) (new-env (capture-env env)))
 396            (if (null? inits)
 397                (eval body new-env)
 398                (lp (cdr inits)
 399                    (cons (eval (car inits) env) new-env)))))
 400
 401         (('lambda (body nreq . tail))
 402          (if (null? 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)
 406                                        0 #f '() #f)
 407                  (apply make-general-closure (capture-env env) body nreq tail))))
 408
 409         (('seq (head . tail))
 410          (begin
 411            (eval head env)
 412            (eval tail env)))
 413
 414         (('lexical-set! (n . x))
 415          (let ((val (eval x env)))
 416            (list-set! env n val)))
 417
 418         (('call-with-values (producer . consumer))
 419          (call-with-values (eval producer env)
 420            (eval consumer env)))
 421
 422         (('apply (f args))
 423          (apply (eval f env) (eval args env)))
 424
 425         (('module-ref var-or-spec)
 426          (variable-ref
 427           (if (variable? var-or-spec)
 428               var-or-spec
 429               (memoize-variable-access! exp #f))))
 430
 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))
 435            (define! name x)
 436            (if #f #f)))
 437
 438         (('toplevel-set! (var-or-sym . x))
 439          (variable-set!
 440           (if (variable? var-or-sym)
 441               var-or-sym
 442               (memoize-variable-access! exp
 443                                         (capture-env (if (pair? env)
 444                                                          (cdr (last-pair env))
 445                                                          env))))
 446           (eval x env)))
 447
 448         (('dynwind (in exp . out))
 449          (dynamic-wind (eval in env)
 450                        (lambda () (eval exp env))
 451                        (eval out env)))
 452
 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))
 457              (if (null? fluids)
 458                  (eval exp env)
 459                  (with-fluids (((car fluids) (car vals)))
 460                    (lp (cdr fluids) (cdr vals)))))))
 461
 462         (('prompt (tag exp . handler))
 463          (@prompt (eval tag env)
 464                   (eval exp env)
 465                   (eval handler env)))
 466
 467         (('call/cc proc)
 468          (call/cc (eval proc env)))
 469
 470         (('module-set! (x . var-or-spec))
 471          (variable-set!
 472           (if (variable? var-or-spec)
 473               var-or-spec
 474               (memoize-variable-access! exp #f))
 475           (eval x env)))))
 476
 477     ;; primitive-eval
 478     (lambda (exp)
 479       "Evaluate @var{exp} in the current module."
 480       (eval
 481        (memoize-expression
 482         (if (macroexpanded? exp)
 483             exp
 484             ((module-transformer (current-module)) exp)))
 485        '()))))