I'm working through the book Structure and implementation of computer programs and in one of the chapters there were some code used to calculate the factorial of a number:
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
Earlier in the book I learned that I can define functions inline in another function like this:
(define (factorial n)
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
(fact-iter 1 1 n))
I know that using the second approach fact-iter won't be accessible outside of the scope of factorial but I was wondering what happens actually when I run the second version of factorial?
A new local binding for the symbol fact-iter gets defined and a new function created or this binding is created only once when the program compiles?
I'm coming from a java background and this is not yet clear for me.
It rather depends on the Scheme implementation (strategies for which are discussed in subsequent chapters of SICP). Conceptually, a new function gets defined/compiled in each call to factorial per your second definition of it. However, a good compiler can transform this code so that it's much more like your first definition.
Since this construct is so common in Scheme (the idiomatic way of writing a loop being the named-let construct, which also defines functions on the fly), Scheme compilers should be pretty good at doing this optimization. And in fact your example is easy to handle for an optimizer since the inner function's definition does not actually depend on any variables bound by the outer function, so it can be lifted out almost as-is (only the name may have to be changed).
It is never the case that a new function gets compiled with each call to factorial. A function is formally a piece of code and an environment; it is the environment that can change with each call. For example:
(define (find x l)
(define (equal-to-x y) (equal? x y))
....)
In the above, every call to 'find' will produce a new function 'equal-to-x'. The 'environment' of the 'equal-to-x' function references a variable 'x' that is defined in another scope. However, a suitably good compiler may notice that equal-to-x is never returned or bound to an out-of-scope variable and thus the compiler may 'inline' the code - thereby not needing a new function (code + environment).
In your code, the free references (+, *, and >) of the internally defined fact-iter (your second case) are all globally defined and the fact-iter function is not returned (or bound). Thus a good enough compiler would inline it.
Here is a case of a not very good compiler. You can see in the disassembly of 'find' that a function/closure (code + environment) is created and in the disassembly of 'ex' that an environment reference is used (to get at 'x').
=> (define find (lambda (x l)
(define ex (lambda (y) (= x y)))
(ex (car l))))
(=>)
=> (sys:disassemble find)
;; Address : 0x00327e90
;; Label : find
;; Constants:
;; 0: #t
;; 1: #[<code> ex 1]
;; 2: (<cons> 6)
;; Code :
;; 0-1: explode 2
;; 2-3: check 2
;; 4-5: get-loc 0
;; 6-8: closure 1, 1
;; 9-10: get-loc 2
;; 11-13: get-loc-res 1, 2
;; 14: cons$car
;; 15-16: call-tail-check 1
;; :
;; Address : 0x0031fb40
;; Label : ex
;; Constants:
;; 0: #t
;; 1: (<number> 1 142 42 154 158)
;; Code :
;; 0-1: explode 1
;; 2-3: check 1
;; 4-6: get-env-res 0, 1
;; 7-9: get-loc-res 0, 1
;; 10: number$=
;; 11-12: return 1
;; :
;; Env :
#[<function> find 2]
