MCE Exercise Solutions: 1. return-first Within mc-eval, we'll need to add a clause to check for our new special form: (define (mc-eval exp env) (cond . . . ((return-first? exp) (eval-return-first exp env)) . . . )) And we'll need to add the appropriate helper procedures: (define (return-first? exp) (tagged-list? exp 'return-first)) (define (return-first-actions exp) (cdr exp)) (define (eval-return-first exp env) (let ((result (mc-eval (first-exp (return-first-actions exp)) env)) ) (eval-sequence (rest-exps (return-first-actions exp)) env) result)) 2. *result* Values are printed to the user in the driver-loop, so this is where we should start with our changes. Since we would like to be able to refer to *result* within expressions such as (/ *result* 2), it would be easiest to make it an ordinary variable in the MCE's global environment. (define (driver-loop) (prompt-for-input input-prompt) (let ((input (read))) (let ((output (mc-eval input the-global-environment))) ;; added the following line (set-variable-value! '*result* output the-global-environment) (announce-output output-prompt) (user-print output))) (driver-loop)) We'll need to define *result* before we can call set-variable-value!. The MCE's global environment is initialized in setup-environment: (define (setup-environment) (let ((initial-env (extend-environment (primitive-procedure-names) (primitive-procedure-objects) the-empty-environment))) (define-variable! 'true true initial-env) (define-variable! 'false false initial-env) (define-variable! '*result* 'no-previous-value initial-env) initial-env)) (It would be better to restrict using *result* to only the top-level; that is, the user should be able to use *result* when entering expressions at the driver-loop prompt, but it doesn't make much sense to refer to in the body of a procedure, for example. Implementing this kind of restriction, however, is probably more trouble than it's worth.) 3. implementing dotted-tail notation Note that we don't need to do anything special to account for using dotted-tail notation with define versus lambda. When we perform the syntactic-sugar transformation on (define (foo . args) ), we will automatically get (define foo (lambda args )). Recall that using dotted-tail notation, for a procedure such as: ((lambda args ) 1 2 3) ARGS will be bound to the list (1 2 3). This involves changing how the MCE binds variables to values, so this is primarily a change to either extend-environment and/or make-frame. The selector procedure-parameters will now return either: * a list (normal usage, such as for (lambda (x) )) * an improper list (at least one required argument, such as for (lambda (x . args) )) * an atom (no required arguments, such as for (lambda args )) We must scan through vars; if we can determine that it is an improper list, we then must package the remaining values into a list and bind it to the corresponding variable. The textbook's implementation of frames makes this a bit more complicated than necessary. (An association list would have been simpler...) (define (extend-environment variables values base-env) (let ((frame (make-frame '() '() )) ) (define (make-bindings! vars vals) (cond ((and (null? vars) (null? vals)) 'done) ((null? vars) (error "Too many arguments supplied" variables values)) ((not (pair? vars)) ;; dotted-tail notation (add-binding-to-frame! vars vals frame)) ((null? vals) (error "Too few arguments supplied" variables values)) (else (add-binding-to-frame! (car vars) (car vals) frame) (make-bindings! (cdr vars) (cdr vals)) ) )) (make-bindings! variables values) (cons frame base-env) )) Alternatively, we could do this without mutation, in a purely functional style: (define (extend-environment variables values base-env) (define (get-frame vars vals) (cond ((and (null? vars) (null? vals)) (make-frame '() '() )) ((null? vars) (error "Too many arguments supplied" variables values)) ((not (pair? vars)) ;; dotted-tail notation (make-frame (list vars) (list vals)) ) ((null? vals) (error "Too few arguments supplied" variables values)) (else (let ((rest-of-frame (get-frame (cdr vars) (cdr vals))) ) (make-frame (cons (car vars) (frame-variables rest-of-frame)) (cons (car vals) (frame-values rest-of-frame)) )) ) )) (cons (get-frame variables values) base-env)) 4. apply We can make the analogy: apply : underlying-Scheme :: mc-apply : meta-Scheme We want a procedure that will take a meta-Scheme procedure and will invoke it on a list of arguments. This is exactly what mc-apply does. Thus, all that's needed is to add mc-apply as a primitive procedure: (define primitive-procedures (list . . . (list 'apply mc-apply) )) 5. truth From footnote 6 on page 367 of the SICP textbook: "Contemplation of the meaning of true? here yields expansion of consciousness without the abuse of substance." (That's supposed to be a joke.) We want to redefine the meaning of truth in the metacircular evaluator. First, we'll need to change all of our primitive predicates to return either 1 or 0: (define primitive-procedures (list . . . (list 'null? (lambda (x) (if (null? x) 1 0)) ) (list '= (lambda (a b) (if (= a b) 1 0)) ) (list 'equal? (lambda (a b) (if (equal? a b) 1 0)) ) . . . )) (We could make this easier by writing a helper procedure similar to make-logo-pred from the Logo project.) We will also need to modify true? and false?--these procedures convert meta-Scheme truth values to underlying-Scheme truth values so that the underlying Scheme system can understand them. (This is necessary for procedures such as eval-if, eval-and, and eval-or to work.) (define (true? x) (not (= x 0)) ) (define (false? x) (= x 0)) 6. representation of procedures and lists The problem is that BOTH procedures and ordinary lists in the MCE are stored as underlying-Scheme lists. This is because we use the underlying Scheme system's cons and list procedures as primitives in the MCE. If we create a list within the metacircular evaluator that happens to start with the symbol PROCEDURE, the underlying system sees this as a tagged-list and cannot differentiate it from a meta-Scheme procedure. Similarly, no problems occur if we try to take the car or cdr of a meta-Scheme procedure. How can we fix this? The underlying Scheme system needs to be able to differentiate meta-Scheme procedures from meta-Scheme lists. We could do this by requiring that pairs/lists be tagged as well, so that a meta-Scheme pair such as (1 . 2) would have an underlying representation: (pair 1 2) and a meta-Scheme list such as (1 2 3) would have an underlying representation: (pair 1 (pair 2 (pair 3 () )))) (We need to have nested tagged-lists so that we don't run into the same bug when dealing with lists of meta-Scheme procedures.)