The machine can report the work its controller performed.
An explicit register-machine executor can count fetched instructions, total stack pushes, and maximum stack depth while preserving the controller result and final stack state.
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.
(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))- Output
- —
- Value
- —
- Diagnostic
- —
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)).
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.
Change the program before you read the hint.
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 one hint
Input 3 creates two recursive levels. Each level pushes continue and n. Excluding halt subtracts one only from the fetched-instruction count.