How Scheme evaluates the man or boy test?

Question

This is the Man or boy test Scheme code:

(define (A k x1 x2 x3 x4 x5)
  (define (B)
    (set! k (- k 1))
    (A k B x1 x2 x3 x4))
  (if (<= k 0)
      (+ (x4) (x5))
      (B)))

In order to simplify the evaluation process, I rewrite it to:

(define (A k x1 x2)
  (define (B)
    (set! k (+ k -1))
    (A k B x1))
  (if (> 1 k)
      (x2)
      (B)))

I can't understand why (A 2 (lambda () 1) (lambda () -1)) return 1.

Can anyone explain how the Scheme interpreter evaluates this expression step by step. If you can attach the environment diagrams, so much the better:)

Answer 1

The question is very subtle, and in the first moment I thought that the call would cause an infinte loop. But the real affair is the following:

Let's start calling F1 and F2 the two functions passed to A the first time, that is

F1 = (lambda() 1)
F2 = (lambda() -1)

So, after the first call of (A 2 F1 F2), A establishes the following environment, that we will name E1:

The test is now false, so A calls B1. B1 first decrements k in E1, then calls again A, passing 1, itself, and x1, which is F1. So this is the call with parameters substituted with their values: (A 1 B1 F1). And the new environment established by this call (E2) is shown in the following picture:

The test is still false, so A calls B2, which first modifies k in E2, then calls A with 0, itself, and x1 (which now is B1). So the call is (A 0 B2 B1), and the new set of environments is now:

The test is now true, so A call x2, which is B1. Now B1 modifies k in its environment (which is E1), and then calls A with 0, itself, and the value of x1, which, in E1, is F1. So the call is (A 0 B1 F1) and the environment established by this call is depicted in the next figure:

And finally, after checking that the test is true, A calls x2, that is F1, which returns 1. At last!