CODEWITHSUNDEEP
schemeracket
anna-k
anna-k

Reputation: 117

Scheme result of a function

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

Upvotes: 2

Views: 300

Answers (5)

Prethia
Prethia

Reputation: 1203

One side note: You need to use an environment model to figure it out.Because the answer of questions like that differs in lexical scoping versus dynamic scoping.

Upvotes: 0

Cam
Cam

Reputation: 15234

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.

Upvotes: 4

Eli Barzilay
Eli Barzilay

Reputation: 29546

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

Upvotes: 3

tster
tster

Reputation: 18237

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

Upvotes: 3

sepp2k
sepp2k

Reputation: 370102

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.

Upvotes: 2

Related Questions