5.2.6 · Machine instrumentation

The machine can report the work its controller performed.

An explicit register-machine executor counts fetched instructions, stack pushes, and maximum stack depth while preserving the controller result.

Guiding question

What can controller-level counters reveal that the final register values alone cannot?

Count every fetched instruction with one explicit convention
Count total save operations without confusing them with current stack depth
Track maximum stack depth while restore operations unwind the stack
Compare the base and recursive paths of the same factorial controller
Keep controller measurements distinct from wall-clock time and hardware profiling

The controller is the same finite recursive factorial machine for every run. Its explicit register vector holds n, val, continue, flag, and pc. A separate list represents the stack. The executor increments instruction-count as soon as it fetches an instruction, including halt. push! increments total-pushes and updates max-depth from the current list length; pop! shortens the live stack but does not erase the historical push count.

With n equal to 1, the branch jumps directly to the base assignment and reaches halt after five fetched instructions with no stack use. With n equal to 3, the controller saves continue and n at two recursive levels, so it performs four pushes, reaches depth four, and fetches 27 instructions before halting with value 6 and an empty stack. These numbers describe this exact controller, input, and counting convention. They are not elapsed time, CPU instructions, allocation cost, or a general profiler.

SICP code3,860 of 1,048,576 UTF-8 bytes

(begin
  (define controller
    (vector
      '(test base? n)
      '(branch 11)
      '(save continue)
      '(save n)
      '(assign n sub1 n)
      '(assign continue constant 7)
      '(goto 0)
      '(restore n)
      '(restore continue)
      '(assign val multiply n val)
      '(goto-register continue)
      '(assign val constant 1)
      '(goto-register continue)
      '(halt)))
  (define (register-index name)
    (cond ((eq? name 'n) 0)
          ((eq? name 'val) 1)
          ((eq? name 'continue) 2)
          ((eq? name 'flag) 3)
          ((eq? name 'pc) 4)))
  (define (run-factorial start)
    (let ((registers (vector start 0 13 #f 0))
          (stack '())
          (instruction-count 0)
          (total-pushes 0)
          (max-depth 0))
      (define (get-register name)
        (vector-ref registers (register-index name)))
      (define (set-register! name value)
        (vector-set! registers (register-index name) value))
      (define (advance!)
        (set-register! 'pc (+ (get-register 'pc) 1)))
      (define (push! value)
        (set! stack (cons value stack))
        (set! total-pushes (+ total-pushes 1))
        (set! max-depth (max max-depth (length stack))))
      (define (pop!)
        (let ((value (car stack)))
          (set! stack (cdr stack))
          value))
      (define (assign-value instruction)
        (let ((operation (caddr instruction)))
          (cond ((eq? operation 'constant)
                 (cadddr instruction))
                ((eq? operation 'sub1)
                 (- (get-register (cadddr instruction)) 1))
                ((eq? operation 'multiply)
                 (* (get-register (cadddr instruction))
                    (get-register (list-ref instruction 4)))))))
      (define (execute remaining-steps)
        (if (= remaining-steps 0)
            'step-limit
            (let* ((instruction
                    (vector-ref controller (get-register 'pc)))
                   (operation (car instruction)))
              (set! instruction-count (+ instruction-count 1))
              (cond
                ((eq? operation 'halt)
                 (list (get-register 'val)
                       instruction-count
                       total-pushes
                       max-depth
                       (length stack)))
                ((eq? operation 'test)
                 (set-register!
                   'flag
                   (= (get-register (caddr instruction)) 1))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'branch)
                 (set-register!
                   'pc
                   (if (get-register 'flag)
                       (cadr instruction)
                       (+ (get-register 'pc) 1)))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'save)
                 (push! (get-register (cadr instruction)))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'restore)
                 (set-register! (cadr instruction) (pop!))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'assign)
                 (set-register! (cadr instruction)
                                (assign-value instruction))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto)
                 (set-register! 'pc (cadr instruction))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto-register)
                 (set-register! 'pc
                                (get-register (cadr instruction)))
                 (execute (- remaining-steps 1)))))))
      (execute 200)))
  ; value, fetched instructions, pushes, max depth, final depth
  (run-factorial 3))

(begin
  (define controller
    (vector
      '(test base? n)
      '(branch 11)
      '(save continue)
      '(save n)
      '(assign n sub1 n)
      '(assign continue constant 7)
      '(goto 0)
      '(restore n)
      '(restore continue)
      '(assign val multiply n val)
      '(goto-register continue)
      '(assign val constant 1)
      '(goto-register continue)
      '(halt)))
  (define (register-index name)
    (cond ((eq? name 'n) 0)
          ((eq? name 'val) 1)
          ((eq? name 'continue) 2)
          ((eq? name 'flag) 3)
          ((eq? name 'pc) 4)))
  (define (run-factorial start)
    (let ((registers (vector start 0 13 #f 0))
          (stack '())
          (instruction-count 0)
          (total-pushes 0)
          (max-depth 0))
      (define (get-register name)
        (vector-ref registers (register-index name)))
      (define (set-register! name value)
        (vector-set! registers (register-index name) value))
      (define (advance!)
        (set-register! 'pc (+ (get-register 'pc) 1)))
      (define (push! value)
        (set! stack (cons value stack))
        (set! total-pushes (+ total-pushes 1))
        (set! max-depth (max max-depth (length stack))))
      (define (pop!)
        (let ((value (car stack)))
          (set! stack (cdr stack))
          value))
      (define (assign-value instruction)
        (let ((operation (caddr instruction)))
          (cond ((eq? operation 'constant)
                 (cadddr instruction))
                ((eq? operation 'sub1)
                 (- (get-register (cadddr instruction)) 1))
                ((eq? operation 'multiply)
                 (* (get-register (cadddr instruction))
                    (get-register (list-ref instruction 4)))))))
      (define (execute remaining-steps)
        (if (= remaining-steps 0)
            'step-limit
            (let* ((instruction
                    (vector-ref controller (get-register 'pc)))
                   (operation (car instruction)))
              (set! instruction-count (+ instruction-count 1))
              (cond
                ((eq? operation 'halt)
                 (list (get-register 'val)
                       instruction-count
                       total-pushes
                       max-depth
                       (length stack)))
                ((eq? operation 'test)
                 (set-register!
                   'flag
                   (= (get-register (caddr instruction)) 1))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'branch)
                 (set-register!
                   'pc
                   (if (get-register 'flag)
                       (cadr instruction)
                       (+ (get-register 'pc) 1)))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'save)
                 (push! (get-register (cadr instruction)))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'restore)
                 (set-register! (cadr instruction) (pop!))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'assign)
                 (set-register! (cadr instruction)
                                (assign-value instruction))
                 (advance!)
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto)
                 (set-register! 'pc (cadr instruction))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto-register)
                 (set-register! 'pc
                                (get-register (cadr instruction)))
                 (execute (- remaining-steps 1)))))))
      (execute 200)))
  ; value, fetched instructions, pushes, max depth, final depth
  (run-factorial 3))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns (6 27 4 4 0). The second returns ((1 1 5 0 0) (2 2 16 2 2) (4 24 38 6 6)).

Trace focus

Follow instruction-count immediately after each vector fetch, including halt. Compare each save with a push increment and a possible max-depth update, then watch restore shorten the current stack without reducing total-pushes. The base path jumps directly to instruction 11, while each additional recursive level contributes two saves and later two restores.

Try it yourself

Change the program and compare the result.

Predict the report for input 3 without running it. Then change the counting convention so halt is not included and explain exactly which field changes.

Show hint

Input 3 creates two recursive levels. Each level pushes continue and n. Excluding halt subtracts one only from the fetched-instruction count.

Complete this lesson

0 of 23 lessons complete in this chapter0%