(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2)))))) (let ((t0 0) (t1 0)) (set! t0 (get-universal-time)) (fib 20) (set! t1 (get-universal-time)) (- t1 t0)) ; 67 without memorization ; 12 with memorization ;;; L-Eval input: (square (id 10)) ;;; L-Eval value: 100 ;;; L-Eval input: count ;;; L-Eval value: 1 ; with memorization, (id 10) is called once. 2 ; without memorization, (id 10) is called twice
If the value of the operator is not forced, this will fail because f is a thunk.
(let ((f (lambda (x) (* x x)))) (f 2)) ;Unknown procedure type -- APPLY (thunk (lambda ... ...) (...))
(define w (id (id 10))) ;;; L-Eval input: count ;;; L-Eval value: 1 ;;; L-Eval input: w ;;; L-Eval value: 10 ;;; L-Eval input: count ;;; L-Eval value: 2
Defining w as (id (id 10)) will cause the eval procedure to be applied to (id (id 10)). So the outer id procedure will be evaluated. And the count variable will be set to 1. Printing the value of w will cause the inner id procedure to be evaluated. So the final value of count will become 2.
It is shown below how to implement unless as a special form.
(define (eval exp env) ; ...... ((unless? exp) (eval (unless->if exp) env)) ; ...... ) (define (unless? exp) (tagged-list? exp 'unless)) (define (unless-clauses exp) (cdr exp)) (define (unless-condition clauses) (car clauses)) (define (unless-usual-value clauses) (cadr clauses)) (define (unless-exceptional-value clauses) (caddr clauses)) (define (unless->if exp) (expand-unless-clauses (unless-clauses exp))) (define (expand-unless-clauses clauses) (make-if (unless-condition clauses) (unless-exceptional-value clauses) (unless-usual-value clauses)))
For the sake of argument, the following code will fail unless unless is implemented as a procedure.
(define (foo f condition value-1 value-2) (f condition value-1 value-2)) (foo unless (> 2 10) 1 2) ; Unbound variable unless ; because unless is a special form (define (unless-proc condition usual-value exceptional-value) (if condition exceptional-value usual-value)) (foo unless-proc (> 2 10) 1 2) ; 1
The code does not work in a normal-order language. The maximum recursion depth will be reached because the evaluation of the second argument of unless will proceed forever.
Below is the code I use for the experiment.
(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) (let ((t0 0) (t1 0)) (define (loop i n) (factorial 1234) (if (< i n) (loop (+ i 1) n))) (set! t0 (get-universal-time)) (loop 0 200) (set! t1 (get-universal-time)) (- t1 t0))
The results are 78 and 41 for the original metacircular evaluator and the improved evaluator, respectively. So the original evaluator spends about 37 seconds on repeating syntactic analysis.
The version of analyze-sequence in the text produces more efficient execution procedure than Alyssa’s version.
The execution procedure produced by the analyze-sequence procedure in the text looks like this:
(lambda (env) ((lambda (env) ((lambda (env) (proc1 env) (proc2 env)) env) (proc3 env)) env) (proc4 env))
Here, proc1, proc2, proc3 and proc4 are the resulting procedures of applying the analyze procedure to individual expressions of a sequence.
The execution procedure produced by Alyssa’s version looks like this:
(lambda (env)
(execute-sequence (proc1 proc2 proc3 proc3) env))
When the above execution procedure is run, procedure execute-sequence is called. Note that procedure execute-sequence contains a cond expression and an iteration process. So it will be less efficient.
(define (analyze exp) ; ...... ((let? exp) (analyze (let->combination exp))) ; ...... )
See SICP Exercise 4.6 for procedures let? and let->combination.
; The evaluation proceeds as follows ((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))))) 10) ;--> ((lambda (fact) (fact fact 10)) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1)))))) ;--> ((lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))) 10) ;--> (if (= 10 1) 1 (* 10 ((lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))) 9))) ;--> (* 10 ((lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))) 9)) ;......
The following expression computes the 10th Fibonacci number.
((lambda (n) ((lambda (fibo) (fibo fibo n)) (lambda (fb k) (cond ((= k 0) 0) ((= k 1) 1) (else (+ (fb fb (- k 1)) (fb fb (- k 2)))))))) 10)
An alternative definition of f:
(define (f x) ((lambda (even? odd?) (even? even? odd? x)) (lambda (ev? od? n) (if (= n 0) true (od? ev? od? (- n 1)))) (lambda (ev? od? n) (if (= n 0) false (ev? ev? od? (- n 1))))))
(define (eval exp env) ; ...... ((letrec? exp) (eval (letrec->let exp) env)) ; ...... ) (define (letrec? exp) (tagged-list? exp 'letrec)) (define (make-unassigned-letrec vars) (if (null? vars) '() (cons (list (car vars) ''*unassigned*) (make-unassigned-letrec (cdr vars))))) (define (make-set-letrec vars exps) (if (null? vars) '() (cons (list 'set! (car vars) (car exps)) (make-set-letrec (cdr vars) (cdr exps))))) (define (letrec->let exp) (let* ((assi (let-assignment exp)) (lvars (let-var assi)) (lexps (let-exp assi))) (cons 'let (cons (make-unassigned-letrec lvars) (append (make-set-letrec lvars lexps) (let-body exp))))))
See SICP Exercise 4.6 for the definitions of let-assignment, let-body, let-var and let-exp.
I am going to skip the environment diagram. But I will explain why Louis Reasoner is wrong. Note that
(let ((even? (lambda (n) <body of even? including call to odd?>) (odd? (lambda (n) <body of odd? including call to even?>))) <rest of body of f>))
is equivalent to
((lambda (even? odd?) <rest of body of f>) (lambda (n) <body of even? including call to odd?>) (lambda (n) <body of odd? including call to even?>))
There are three lambda functions in the above piece of code. The arguments even? and odd? of the first lambda function have no relationship whatsoever with odd? in the body of the second lambda function and even? in the body of the third lambda function. The way I see it, the arguments even? and odd? of the first lambda function are just names. We can rename them to foo and bar if we like. Therefore the above code will not work. Louis Reasoner is wrong.
