Normal order and applicative order evaluation in Scheme

Question

Hi All,

For the 1st example given on site: View-Site, my understanding is that normal order evaluates to [6;1;1] and applicative order evaluates to [6;2;2]

Can anyone please confirm my assessment?

Regards,
darkie

Answer 1

Ok, let's go through the steps of evaluating (cons res v) with normal-order evaluation:

v has been defined as (cons a (cons b ’())), so we have cons res (cons a (cons b ’())). res is defined as (foo ...), so we have

(cons (foo (begin (set! a (+ a 1)) a)
           (begin (set! b (* b 2)) b))
      (cons a (cons b ’())))

Lastly foo x y is defined as (+ x y y), so by substituting (begin (set! a (+ a 1)) a) for x and (begin (set! b (* b 2)) b) for y, we get:

(cons (+ (begin (set! a (+ a 1)) a)
         (begin (set! b (* b 2)) b)
         (begin (set! b (* b 2)) b))
      (cons a (cons b ’())))

So now let's evaluate this: To get the result of cons, we first need to evaluate its first argument, (+ ...). So we first need to evaluate the first argument of + which is (begin (set! a (+ a 1)) a). This evaluates to 2, so the value of a is now 2 and the first argument to + is also 2. Now we do the same thing with the second argument. This also evaluates to 2 and sets b to 2. The third argument is (begin (set! b (* b 2)) b) again, so the value of b is now 4 and the third argument is 4. So the first argument to cons is the result (+ 2 2 4), which is 8 and the values of a and b are 2 and 4.

Now we need to evaluate the second argument, (cons a (cons b ’())). So since the value of a and b are 2 and 4, the end result is (8 2 4).