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

Question

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?

Answer 1

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.

Answer 2

In one word: negligible. Using nested functions instead of top-level defined functions won't have a noticeable effect on performance, we use nested functions ("block structure" in SICP's terms) for clarity and better structuring a procedure, not for efficiency:

Such nesting of definitions, called block structure, is basically the right solution to the simplest name-packaging problem

There might be a small difference in the time it takes to look up a function depending on where it was defined, but that will depend on implementation details of the interpreter. It's not worth worrying about it.

Answer 3

It's implementation dependent. It does not say anything about how much cost a closure should have, but since Scheme is designed around closures any implementation should stride to make closures cheap. Many implementations does CPS conversions and that introduces a closure per evaluation operation.

There is a compiler technique called lambda lifting where local functions get transformed to global by changing free variables not in global scope to bounded ones and lifting the procedure out of the procedure it was defined in. The SICP code might get translated to something like:

(define (lift:good-enough? x guess)
  (< (abs (- (square guess) x)) 0.001))

(define (lift:improve x guess)
  (average guess (/ x guess)))

(define (lift:sqrt-iter x guess)
  (if (lift:good-enough? x guess)
      guess
      (lift:sqrt-iter (lift:improve x guess))))

(define (sqrt x)  
  (lift:sqrt-iter x 1.0))

Where all the lift:-prefixed identifiers are unique so that it does not collide with existing global bindings.

Answer 4

Not relevant.

One of the important aspects of designing a programming language is often choosing between efficiency on one side, and expressiveness on the other side. In most situations these two aspects defines the charactersistics of a low-level and high-level language, respectively.

Scheme is a small, but powerful high-level language from the family of Lisp languages. One of the most powerful feature of Scheme is it's expressiveness and ability to abstract. As a programmer of Scheme you use block structure inside procedures because it encapsulates related behaviour and solves your problem in a structured way, but you don't consider low-level properties of this behaviour, such as runtime-cost of calling procedures or allocating lists. This is part of the joy of programming in a high-level language such as Scheme.

As you say: It's amazing and useful, so continue your work and create something nice. Until the program becomes considerably slow in operation I wouldn't care about these things and just concentrate on the harder problems like defining concepts and behaviour in your program.