Search code examples
schemefunction-callnested-function

how is the efficiency and cost of nested function in scheme language


In SICP, I have learned using functions, it's amazing and usefull. But I am confused with the cost of function nested, like below code:

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
     (if (good-enough? guess)
       guess
       (sqrt-iter (improve guess))))
 (sqrt-iter 1.0))

It defines three child-functions, how is the efficiency and cost? If I use more function calls like this?

UPDATE: look at code below, in Searching for divisors

(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

Q1: the divides? and smallest-divisor are not necessary, just for clarification. How are the efficiency and cost? Does Scheme compiler optimize for this situation. I think I should learn some knowledge about compiler.(͡๏̯͡๏)

q2: How about in interpreter?


Solution

  • The efficiency question breaks down to a question of compiler optimization. Generally anytime you have a lexical procedure, such as your improve procedure, that references a free variable, such as your x, then a closure needs to be created. The closure has an 'environment' that must be allocated to store all free variables. Thus there is some space overhead and some time overhead (to allocate the memory and to fill the memory).

    Where does compiler optimization come to play? When a lexical procedure does not 'escape' its lexical block, such as all of yours, then the compiler can inline the procedures. In that case a closure with its environment need not be created.

    But, importantly, in every day use, you shouldn't worry about the use of lexical procedures.