Scheme result of a function

Question

Hello, I have met the following code in Scheme:

(define x! 
  (lambda(x)
    (if (= x 1) 1 (* x (x! (- x 1))))))

(define fact x!)

(define x! (lambda (x) x))
(fact 5)

Everything is clear for me until re-defining x! and seeing the result of the function (20). How can it be explained?.. Why is it 20 and not 5!= 120. Thanks in advance

Answer 1

Ok, what happens here is the following:

When you do (x! (- x 1)) inside the original definition of x!, you're calling the function named x!. So if you change what the name x! means, that will affect this call to x!.

When you do (define fact x!) fact doesn't refer to the name x!, but to the current contents of x!, i.e. the function you just defined.

Now you change the meaning of the name x! and then call (fact 5). This will first invoke the original definition of x! (because that's what fact refers to), however when it gets to the call (x! (- 5 1)), it invokes the new definition of x!, which returns 4, so you get 5*4 = 20.

Answer 2

first you define x! to be the way to compute factorial (i.e. (x! 5) = 120).
Then you define fact to be what x! is, which is the same function (i.e. fact = lambda(x) (if (= x 1)... Then you change what x! is the identity. However, fact is still that same function, you didn't change it, but that function references x! internally, so it ends up calling fact (which is the first thing you defined) which calls the identity function.

so (fact 5) is the same as:

(if (= 5 1) 1 (* 5 (x! (- 5 1))))))

which is the same as:

(if false 1 (* 5 (x! 4)))

which is the same as:

(if false 1 (* 5 4))

which is the same as:

(* 5 4)

which is 20

Answer 3

The way Scheme behaves when you have a redefinition of an identifier is to use set! for it. In your case, if you replace the redefinition with

(set! x! (lambda (x) x))

then the result will become clearer.

(Note that this is not something that all schemes do...)

Answer 4

Here's what's happening:

When you (define fact x!), you aren't permanently linking fact to x!. You're making fact equal to whatever x! is at the time of fact's definition.

So (define fact x!) is actually equivalent to:

(define fact
  (lambda(x)
    (if (= x 1) 1 (* x (x! (- x 1))))))

Next, you redefine x!:

(define x! (lambda (x) x))

But that does not change fact - it only changes x!. Next, you do this:

(fact 5)

---

Here's what the interpreter 'does' next (it may actually do it slightly differently - but only trivially so, and this should at least help you understand the behaviour of your program):

Replacing fact with its definition gives:

(lambda(x)
    (if (= x 1) 1 (* x (x! (- x 1)))))

Replacing x! with its new definition gives:

((lambda(x)
   (if (= x 1)
       1
       (* x 
          (- ((lambda (x)
                x)
              x)
             1))))
 5)

...Simplifying gives:

((lambda(x)
   (if (= x 1)
       1
       (* x (- x 1))))
 5)

...

(if (= 5 1)
    1
    (* 5 (- 5 1)))

...

(if #f
    1
    (* 5 (- 5 1)))

...Resolving the conditional and simplifying the substraction gives:

(* 5 4)

...Which yields 20.