CS 22

Clab 37: Efficient evaluation

Well, we have been lazy. Now let's try to be efficient.
Copy /home/cfk/pub/cs22/week12/aneval to your week13 directory.

This is the analyzing evaluator discussed in section 4.1.7. We'll load it and do a few evaluations and then look at the-global-environment.

metacircular-evaluator-loaded analyzing-metacircular-evaluator-loaded > (driver-loop) ;;; M-Eval input: (define x 40) ;;; M-Eval value: ok ;;; M-Eval input: (define (square x) (* x x)) ;;; M-Eval value: ok ;;; M-Eval input: (square x) ;;; M-Eval value: 1600 ;;; M-Eval input: (define (factorial n) (cond ((= n 1) 1) (else (* n (factorial (- n 1)))) ) ) ;;; M-Eval value: ok ;;; M-Eval input: (factorial 4) ;;; M-Eval value: 24 ;;; M-Eval input: q /home/cfk/cs22/week12/mceval.scm: 257.9-257.39: Unbound variable q > the-global-environment #1=(((factorial square x false true car cdr cons null? list memq member not + - * / = > >= <= < abs remainder integer? sqrt eq?) (procedure (n) #<procedure> #1#) (procedure (x) #<procedure> #1#) 40 #f #t (primitive #<primitive:car>) (primitive #<primitive:cdr>) (primitive #<primitive:cons>) (primitive #<primitive:null?>) (primitive #<primitive:list>) (primitive #<primitive:memq>) (primitive #<primitive:member>) (primitive #<primitive:not>) (primitive #<primitive:+>) (primitive #<primitive:->) (primitive #<primitive:*>) (primitive #<primitive:/>) (primitive #<primitive:=>) (primitive #<primitive:>>) (primitive #<primitive:>=>) (primitive #<primitive:<=>) (primitive #<primitive:<>) (primitive #<primitive:abs>) (primitive #<primitive:remainder>) (primitive #<primitive:integer?>) (primitive #<primitive:sqrt>) (primitive #<primitive:eq?>))) Note that fact and square are bound to the lists: (procedure (n) #<procedure> #1#) (procedure (x) #<procedure> #1#) , respectively.

The procedures embedded in these lists are drscheme procedures, that is procedures in our underlying machine language if you will. They are not mceval procedures. We can test this by using drschemes apply which mceval saved as apply-in-underlying-scheme. Recall that apply-in-underlying-scheme takes two parameters, a function and a list of arguments. It applies the function to the arguments.

> (apply-in-underlying-scheme + '(2 3)) 5 > (lookup-variable-value 'factorial the-global-environment) #2=(procedure (n) #<procedure> #4=(((factorial square x false true car cdr cons null? list memq member not + - * / = > >= <= < abs remainder integer? sqrt eq?) #2# (procedure (x) #<procedure> #4#) 40 #f #t (primitive #<primitive:car>) (primitive #<primitive:cdr>) (primitive #<primitive:cons>) (primitive #<primitive:null?>) (primitive #<primitive:list>) (primitive #<primitive:memq>) (primitive #<primitive:member>) (primitive #<primitive:not>) (primitive #<primitive:+>) (primitive #<primitive:->) (primitive #<primitive:*>) (primitive #<primitive:/>) (primitive #<primitive:=>) (primitive #<primitive:>>) (primitive #<primitive:>=>) (primitive #<primitive:<=>) (primitive #<primitive:<>) (primitive #<primitive:abs>) (primitive #<primitive:remainder>) (primitive #<primitive:integer?>) (primitive #<primitive:sqrt>) (primitive #<primitive:eq?>)))) > > (caddr (lookup-variable-value 'factorial the-global-environment)) #<procedure> > (apply-in-underlying-scheme (caddr (lookup-variable-value 'factorial the-global-environment)) (list (extend-environment '(n) '(5) the-global-environment))) 120 Now let's compare this to what mceval would have given us at the same point. > the-global-environment #1=(((factorial square x false true car cdr cons null? list memq member not + - * / = > >= <= < abs remainder integer? sqrt eq?) (procedure (n) ((cond ((= n 1) 1) (else (* n (factorial (- n 1)))))) #1#) (procedure (x) ((* x x)) #1#) 40 #f #t (primitive #<primitive:car>) (primitive #<primitive:cdr>) (primitive #<primitive:cons>) (primitive #<primitive:null?>) (primitive #<primitive:list>) (primitive #<primitive:memq>) (primitive #<primitive:member>) (primitive #<primitive:not>) (primitive #<primitive:+>) (primitive #<primitive:->) (primitive #<primitive:*>) (primitive #<primitive:/>) (primitive #<primitive:=>) (primitive #<primitive:>>) (primitive #<primitive:>=>) (primitive #<primitive:<=>) (primitive #<primitive:<>) (primitive #<primitive:abs>) (primitive #<primitive:remainder>) (primitive #<primitive:integer?>) (primitive #<primitive:sqrt>) (primitive #<primitive:eq?>))) > Here fact and square are bound to the lists: (procedure (n) ((cond ((= n 1) 1) (else (* n (factorial (- n 1)))))) #1#) (procedure (x) ((* x x)) #1#) , respectively.

The procedure bodies embedded in these (mceval) lists are source code for mceval. In mceval, every time factorial is called the body of factorial must be reanalyzed before it can be evaluated. To see this let's work in mceval and aneval side-by-side. Do an execute in mceval and then in the interaction window do:

metacircular-evaluator-loaded > (require-library "trace.ss") > (trace eval apply) Now do an execute in aneval and then in the interaction window do: metacircular-evaluator-loaded analyzing-metacircular-evaluator-loaded > (require-library "trace.ss") > (trace eval apply analyze execute-application analyze-application) We will be tracing a lot more functions in aneval to be fair. Thus, you might expect more lines of output from the aneval trace. But watch what happens. Now in each interaction window alternately define and run: (define (square x) (* x x)) (define (factorial n) (cond ((= n 1) 1) (else (* n (factorial (- n 1)))) ) ) (square 5) (factorial 5) I got 763 lines in the aneval trace and 5668 lines in the mceval trace. The environment takes about 47 lines each time it is printed. I tried cutting out all but about 4 lines of the environment in each trace. Then I had 269 lines left in the aneval trace and 1349 lines left in the mceval trace. mceval has something like 5 times the overhead in doing this set of computations. That does NOT mean that an aneval execution of factorial will be five times faster than an mceval execution of factorial, because a significant part of the computation time is taken by the actual operations, like multipying which is the same for both both executions. But it is likely that an aneval execution will run faster. It will be a lot faster if a process consists of very simple computations and lots of syntactic analysis. It will be just a little faster if time of the actual calculations is high in proportion to the amount of syntax analysis (as is the case for factorial applied to large numbers).

Look up time in the help desk and click on 'time, machine' to read about current-process-milliseconds. One should not bet too much on these timings, but properly interpreted, they can give us useful information. We can get some timings by altering our driver-loop:

(define (driver-loop) (prompt-for-input input-prompt) (let ((input (read)) (start (current-process-milliseconds)) ) (let ((output (eval input the-global-environment)) (stop (current-process-milliseconds))) (announce-output output-prompt) (user-print output) (newline) (display "elapsed time = " ) (display (- stop start)))) (driver-loop)) I changed the driver-loop in mceval for timing and wrote it to to mcevaltime.scm. I also changed the load in aneval to (load "mcevaltime.scm") and wrote it as anevaltime.scm. Try running each on the definition of factorial and (factorial 200) about three times each. Note the running times. Here are some typical runs with anevaltime: Welcome to DrScheme, version 100. Language: MrEd Debug. metacircular-evaluator-loaded analyzing-metacircular-evaluator-loaded > (driver-loop) ;;; M-Eval input: (define (factorial n) (cond ((= n 1) 1) (else (* n (factorial (- n 1)))) ) ) ;;; M-Eval value: ok elapsed time = 0 ;;; M-Eval input: (factorial 7) ;;; M-Eval value: 5040 elapsed time = 10 ;;; M-Eval input: (factorial 200) ;;; M-Eval value: 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000 elapsed time = 130 Here are the same with mcevaltime: Welcome to DrScheme, version 100. Language: MrEd Debug. metacircular-evaluator-loaded > (driver-loop) ;;; M-Eval input: (define (factorial n) (cond ((= n 1) 1) (else (* n (factorial (- n 1)))) ) ) ;;; M-Eval value: ok elapsed time = 0 ;;; M-Eval input: (factorial 7) ;;; M-Eval value: 5040 elapsed time = 10 ;;; M-Eval input: (factorial 200) ;;; M-Eval value: 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000 elapsed time = 260 Now I want you to take a look at a very interesting function. Mathematicians like the successor function a lot. In some sense, a great deal of mathematics can be built from recursion and the successor function. Here we will use successor and predecessor to build an interesting function first discovered last century by Ackermann. Put this in a drscheme definition window. (define pred (lambda (x) (- x 1))) (define succ (lambda (x) (+ x 1))) (define (A z x y) (cond ((= z 0) (if (= x 0) y (succ (A 0 (pred x) y)))) ((= x 0) (if (= z 1) 0 1)) (else (A (pred z) (A z (pred x) y) y)))) (require-library "trace.ss") This is only for natural numbers, so x, y, z should always be non-negative. Now try a couple of evaluations for small values of z (<= 2) and small x and y (<= 10).

  1. Suppose you define a(x, y) = (A 0 x y). What is a(x, y) ? You know it under another name.
  2. Suppose you define m(x, y) = (A 1 x y). What is m(x, y) ? You know it under another name.
  3. Suppose you define e(x, y) = (A 2 x y). What is e(x, y) ? You know it under another name.
  4. You probably don't know another name for (A 3 x y). But can you describe it in terms of x and y? THINK.
Now put trace on pred and succ. With trace on, try evaluations of (A 1 4 5) and (A 2 3 4) in ordinary drscheme. Think about what you get.

Then contrast the results you get when you evaluate (A 2 7 2) in the driver-loop of mcevaltime a couple of times and in anevaltime a couple of times. Analyzing first is good!