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!

Answer 2

I recommend examining the program in the Stepper in DrRacket. The Stepper allows you to examine the individual steps in the computation. You can even go back.

Only problem is that the program as-is can not be run in the stepper. I have therefore made a slight variation, which I hope is close enough.

(define (A k x1 x2)
  (local [(define (B _) (A (- k 1) B x1))]
    (if (< k 2) (x2 '_) (B '_))))

(A 2 (lambda (_) 1) (lambda (_) -1))

The program would in normal Scheme be:

(define (A k x1 x2)
  (define (B _) (A (- k 1) B x1))
  (if (< k 2) (x2 '_) (B '_)))

but the teaching languages require you use use local to make local definitions. Also I have added the argument _ to B. It is never used. The teaching languages require at least one argument, so I add one and just ignore it.

Here is a screen shot of how one step is computed: