sicp-ex-5.45



<< Previous exercise (5.44) | Index | Next exercise (5.46) >>


meteorgan

  
  
 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 

Rptx

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)))))