<< Previous exercise (5.14) | Index | Next exercise (5.16) >>
There is a roughly linear relationship between the number of instructions executed and input n.
But in fact, as the input n increases, the ratio also gradually increases, which shows that it is not a strictly linear relationship between the number of instructions executed and input n.
(define (make-stack)
(let ((s '())
(number-pushes 0)
(max-depth 0)
(current-depth 0))
(define (push x)
(set! s (cons x s))
(set! number-pushes (+ 1 number-pushes))
(set! current-depth (+ 1 current-depth))
(set! max-depth (max current-depth max-depth)))
(define (pop)
(if (null? s)
(error "Empty stack -- POP" 'pop)
(let ((top (car s)))
(set! s (cdr s))
(set! current-depth (- current-depth 1))
top)))
(define (initialize)
(set! s '())
(set! number-pushes 0)
(set! max-depth 0)
(set! current-depth 0)
'done)
(define (print-statistics)
(newline)
(for-each display (list "total-pushes: " number-pushes
"\n"
"maximum-depth: " max-depth
"\n"
)))
(define (dispatch message)
(cond ((eq? message 'push) push)
((eq? message 'pop) (pop))
((eq? message 'initialize) (initialize))
((eq? message 'print-statistics)
(print-statistics))
(else
(error "Unknown request -- STACK" message))))
dispatch))
(define (make-new-machine)
(let ((pc (make-register 'pc))
(flag (make-register 'flag))
(stack (make-stack))
(the-instruction-sequence '())
(the-instruction-counter 0))
(let ((the-ops
(list (list 'initialize-stack
(lambda () (stack 'initialize)))
;;**next for monitored stack (as in section 5.2.4)
;; -- comment out if not wanted
(list 'print-stack-statistics
(lambda () (stack 'print-statistics)))))
(register-table
(list (list 'pc pc) (list 'flag flag))))
(define (allocate-register name)
(if (assoc name register-table)
(error "Multiply defined register: " name)
(set! register-table
(cons (list name (make-register name))
register-table)))
'register-allocated)
(define (lookup-register name)
(let ((val (assoc name register-table)))
(if val
(cadr val)
(error "Unknown register:" name))))
(define (execute)
(let ((insts (get-contents pc)))
(if (null? insts)
'done
(begin
((instruction-execution-proc (car insts)))
(set! the-instruction-counter (+ the-instruction-counter 1))
(execute)))))
(define (dispatch message)
(cond ((eq? message 'start)
(set-contents! pc the-instruction-sequence)
(execute))
((eq? message 'install-instruction-sequence)
(lambda (seq) (set! the-instruction-sequence seq)))
((eq? message 'allocate-register) allocate-register)
((eq? message 'get-register) lookup-register)
((eq? message 'install-operations)
(lambda (ops) (set! the-ops (append the-ops ops))))
((eq? message 'stack) stack)
((eq? message 'operations) the-ops)
((eq? message 'counter) the-instruction-counter)
((eq? message 'reset-counter) (set! the-instruction-counter 0))
(else (error "Unknown request -- MACHINE" message))))
dispatch)))
(define factorial-machine
(make-machine
'(continue n val)
(list (list '= =) (list '* *) (list '- -))
'(
(perform (op initialize-stack))
(assign continue (label factorial-done))
factorial-loop
(test (op =) (reg n) (const 0))
(branch (label base-case))
(test (op =) (reg n) (const 1))
(branch (label base-case))
(save continue)
(save n)
(assign continue (label after-factorial))
(assign n (op -) (reg n) (const 1))
(goto (label factorial-loop))
after-factorial
(restore n)
(restore continue)
(assign val (op *) (reg val) (reg n))
(goto (reg continue))
base-case
(assign val (const 1))
(goto (reg continue))
factorial-done
(perform (op print-stack-statistics))
)))
(define (driver-loop)
(newline)
(let ((n (read)))
(if (eq? n 'quit)
'goodbye
(begin (set-register-contents! factorial-machine 'n n)
(start factorial-machine)
(display "counter: ")
(display (factorial-machine 'counter))
(newline)
(display "value: ")
(display (get-register-contents factorial-machine 'val))
(newline)
(display "ratio of counter to n: ")
(display (/ (/ (factorial-machine 'counter) 1.0) n))
(newline)
(factorial-machine 'reset-counter)
(driver-loop)))))
;;;test data
5
total-pushes: 8
maximum-depth: 8
counter: 61
value: 120
ratio of counter to n: 12.2
10
total-pushes: 18
maximum-depth: 18
counter: 126
value: 3628800
ratio of counter to n: 12.6
20
total-pushes: 38
maximum-depth: 38
counter: 256
value: 2432902008176640000
ratio of counter to n: 12.8
50
total-pushes: 98
maximum-depth: 98
counter: 646
value: 30414093201713378043612608166064768844377641568960512000000000000
ratio of counter to n: 12.92
meteorgan