sicp-ex-5.45

  
  
 compiled: 
 n       total-pushes    maximum-depth 
 2            13                      5 
 3            19                      8 
 4            25                     11 
 so, total-pushes is 6n+1, maximum-depth is 3n-1. 
 total-pushes: 
 compiled/interpretation: (6n+1)/(32n-16) -> 0.1875 
 special/interpretation:     (2n-2)/(32n-16) -> 0.0625 
 maximum-depth: 
 compiled/interpretation: (3n-1)/(5n+3) -> 0.6 
 special/interpretation:     (2n-2)/(5n+3) -> 0.4 

A recommendation I can think of is seeing the code produced by compiling the fact procedure, we can see there are extra saves and pushes generated because compile-proc-appl declares all registers as modified even if the actual procedure does not modify any. Maybe this procedure could be enhanced to avoid this. And declare register usage depending on the operator. With this idea I got the compiler down to 2n+1 pushes and 2n-2 depths. Just as good as the special purpose hand-coded factorial machine.

  
 ;; You also need to modify the caller to pass the operator of the  
 ;; expression down to compile-proc-appl 
 (define safe-ops 
   '(=)) 
 (define (compile-proc-appl op target linkage compile-time-environment) 
   (let ((modified-regs (if (memq op safe-ops) 
                           '() 
                           all-regs))) 
    (cond ((and (eq? target 'val) (not (eq? linkage 'return))) 
           (make-instruction-sequence 
            '(proc) modified-regs 
            `((assign continue (label ,linkage)) 
              (assign val (op compiled-procedure-entry) 
                      (reg proc)) 
              (goto (reg val))))) 
          ((and (not (eq? target 'val)) 
                (not (eq? linkage 'return))) 
           (let ((proc-return (make-label 'proc-return))) 
             (make-instruction-sequence 
              '(proc) modified-regs 
              `((assign continue (label ,proc-return)) 
                (assign val (op compiled-procedure-entry) 
                        (reg proc)) 
                (goto (reg val)) 
                ,proc-return 
                (assign ,target (reg val)) 
                (goto (label ,linkage)))))) 
          ((and (eq? target 'val) (eq? linkage 'return)) 
           (make-instruction-sequence 
            '(proc continue) modified-regs 
            '((assign val (op compiled-procedure-entry) 
                      (reg proc)) 
              (goto (reg val))))) 
          ((and (not (eq? target 'val)) 
                (eq? linkage 'return)) 
           (error "return linkage, target not val -- COMPILE" 
                  target))))) 

Part A
======

┌─────────────────────┬──────────────────┬──────────────────┐
│                     │   Maximum Depth  │ Number of Pushes │
├─────────────────────┼──────────────────┼──────────────────┤
│  Recursive Compiled │      2n +  1     │      2n +  -2    │
├─────────────────────┼──────────────────┼──────────────────┤
│  Iterative Compiled │      0n +  5     │      2n +  11    │
├─────────────────────┼──────────────────┼──────────────────┤
│   Recursive Machine │      2n + -2     │      2n +  -2    │
├─────────────────────┼──────────────────┼──────────────────┤
│ Recursive Evaluator │      5n +  3     │     32n + -10    │
├─────────────────────┼──────────────────┼──────────────────┤
│ Iterative Evaluator │      0n + 10     │     35n +  35    │
└─────────────────────┴──────────────────┴──────────────────┘

This suggests that the compiled code would run 16 times faster, using 60%
less space than purely evaluated code.


Part B
======

The compiler generates code that is effectively as effecient as the hand-
tailored version.  Presumeably because the compiler implements the
optimizations from this section such as open-code application of primitives.