9.7. A Meta-Circular Interpreter for Scheme


9.7. A Meta-Circular Interpreter for Scheme

The program described in this section is a meta-circular interpreter for Scheme, i.e., it is an interpreter for Scheme written in Scheme. The interpreter shows how small Scheme is when the core structure is considered independently from its syntactic extensions and primitives. It also illustrates interpretation techniques that can be applied equally well to languages other than Scheme.

The relative simplicity of the interpreter is somewhat misleading. An interpreter for Scheme written in Scheme can be quite a bit simpler than one written in most other languages. Here are a few reasons why this one is simpler.

  • Tail calls are handled properly only because tail calls in the interpreter are handled properly by the host implementation. All that is required is that the interpreter itself be tail-recursive.

  • First-class procedures in interpreted code are implemented by first-class procedures in the interpreter, which in turn are supported by the host implementation.

  • First-class continuations created with call/cc are provided by the host implementation's call/cc.

  • Primitive procedures such as cons and assq and services such as storage management are provided by the host implementation.

Converting the interpreter to run in a language other than Scheme may require explicit support for some or all of these items.

The interpreter stores lexical bindings in an environment, which is simply an association list (see page 6.3). Evaluation of a lambda expression results in the creation of a procedure within the scope of variables holding the environment and the lambda body. Subsequent application of the procedure combines the new bindings (the actual parameters) with the saved environment.

The interpreter handles only the core syntactic forms described in Section 3.1, and it recognizes bindings for only a handful of primitive procedures. It performs no error checking.

 (interpret 3)  3 (interpret '(cons 3 4))  (3 . 4) (interpret   '((lambda (x . y)       (list x y))     'a 'b 'c 'd))  (a (b c d)) (interpret   '(((call/cc (lambda (k) k))      (lambda (x) x))     "HEY!"))  "HEY!" (interpret   '((lambda (memq)       (memq memq 'a '(b c a d e)))     (lambda (memq x ls)       (if (null? ls) #f           (if (eq? (car ls) x)               ls               (memq memq x (cdr ls)))))))  (a d e) (interpret   '((lambda (reverse)       (set! reverse         (lambda (ls new)           (if (null? ls)               new               (reverse (cdr ls) (cons (car ls) new)))))       (reverse '(a b c d e) '())) #f))  (e d c b a) --------------------------------------------------------------------------- (define interpret #f) (let ()   ;; primitive-environment contains a small number of primitive   ;;procedures; it can be extended easily with additional primitives.   (define primitive-environment     '((apply . ,apply) (assq . ,assq) (call/cc . ,call/cc)           (car . ,car) (cadr . ,cadr) (caddr . ,caddr)           (cadddr . ,cadddr) (cddr . ,cddr) (cdr . ,cdr)           (cons . ,cons) (eq? . ,eq?) (list . ,list)           (map . ,map) (memv . ,memv) (null? . ,null?)           (pair? . ,pair?) (read . ,read) (set-car! . ,set-car!)           (set-cdr! . ,set-cdr!) (symbol? . ,symbol?))) ;; new-env returns a new environment from a formal parameter ;;specification, a list of actual parameters, and an outer ;;environment. The symbol? test identifies "improper" ;; argument lists. Environments are association lists, ;; associating variables with values. (define new-env   (lambda (formals actuals env)     (cond       ((null? formals) env)       ((symbol? formals) (cons (cons formals actuals) env))       (else       (cons (cons (car formals) (car actuals))             (new-env (cdr formals) (cdr actuals) env)))))) ;; lookup finds the value of the variable var in the environment ;;env, using assq. Assumes var is bound in env. (define lookup   (lambda (var env)     (cdr (assq var env)))) ;; assign is similar to lookup but alters the binding of the ;;variable var by changing the cdr of the association pair (define assign   (lambda (var val env)     (set-cdr! (assq var env) val))) ;; exec evaluates the expression, recognizing all core forms. (define exec   (lambda (exp env)     (cond       ((symbol? exp) (lookup exp env))       ((pair? exp)       (case (car exp)         ((quote) (cadr exp))         ((lambda)          (lambda vals            (let ((env (new-env (cadr exp) vals env)))              (let loop ((exps (cddr exp)))                (if (null? (cdr exps))                    (exec (car exps) env)                    (begin                       (exec (car exps) env)                       (loop (cdr exps))))))))       ((if)        (if (exec (cadr exp) env)        (exec (caddr exp) env)        (exec (cadddr exp) env)))        ((set!)         (assign (cadr exp)                 (exec (caddr exp) env)                 env))        (else         (apply (exec (car exp) env)                (map (lambda (x) (exec x env))                     (cdr exp))))))       (else exp)))) ;; interpret starts execution with the primitive environment. (set! interpret   (lambda (exp)     (exec exp primitive-environment)))) 

Exercise 9.7.1.

start example

As written, the interpreter cannot interpret itself because it does not support several of the syntactic forms used in its implementation: let (named and unnamed), internal define, case, cond, and begin. Rewrite the code for the interpreter, using only core syntactic forms.

end example

Exercise 9.7.2.

start example

After completing the preceding exercise, use the interpreter to run a copy of the interpreter, and use the copy to run another copy of the interpreter. Repeat this process to see how many levels deep it will go before the system grinds to a halt.

end example

Exercise 9.7.3.

start example

At first glance, it might seem that the lambda case could be written more simply as follows.

 ((lambda)  (lambda vals    (let ((env (new-env (cadr exp) vals env)))      (let loop ((exps (cddr exp)))        (let ((val (exec (car exps) env)))          (if (null? (cdr exps))              val              (loop (cdr exps)))))))) 

Why would this be incorrect? [Hint: What property of Scheme would be violated?]

end example

Exercise 9.7.4.

start example

Try to make the interpreter more efficient by looking for ways to ask fewer questions or to allocate less storage space. [Hint: Before evaluation, convert lexical variable references into (access n), where n represents the number of values in the environment association list in front of the value in question.]

end example

Exercise 9.7.5.

start example

Scheme evaluates arguments to a procedure before applying the procedure and applies the procedure to the values of these arguments (call-by-value). Modify the interpreter to pass arguments unevaluated and arrange to evaluate them upon reference (call-by-name). [Hint: Use lambda to delay evaluation.] You will need to create versions of the primitive procedures (car, null?, etc.) that take their arguments unevaluated.

end example




The Scheme Programming Language
The Scheme Programming Language
ISBN: 026251298X
EAN: 2147483647
Year: 2003
Pages: 98

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net