Exercise1-19 <---> Exercise1-21

Exercise 1.20

It is easy to express Euclid's Algorithm as a procedure:

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative gcd procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed in section 1.1.5. (The normal-order-evaluation rule for if is described in Exercise1-5) Using the substitution method (for normal order), illustrate the process generated in evaluating (gcd 206 40) and indicate the remainder operations that are actually performed. How many remainder operations are actually performed in the normal-order evaluation of (gcd 206 40)? In the applicative-order evaluation?

Ru: Процесс, порождаемый процедурой, разумеется, зависит от того, по каким правилам работает интерпретатор. В качестве примера рассмотрим итеративную процедуру gcd, приведенную выше. Предположим, что мы вычисляем эту процедуру с помощью нормального порядка, описанного в разделе 1.1.5. (Правило нормального порядка вычислений для if описано в упражнении 1.5.) Используя подстановочную модель для нормального порядка, проиллюстрируйте процесс, порождаемый при вычислении (gcd 206 40) и укажите, какие операции вычисления остатка действительно выполняются. Сколько операций remainder выполняется на самом деле при вычислении (gcd 206 40) в нормальном порядке? При вычислении в аппликативном порядке?

Solution:

Let's illustrate normal evaluation process (remainder is shortened for rem, because stanzas get too long quickly):

(gcd 206 40)
(gcd 40 (rem 206 40)) 
;; we evaluate (rem 206 40) to compare with 0 while evaluating if's condition, but inside function
;; remainder is still unevaluated and is passed again in function as parameter b
(gcd (rem 206 40) (rem 40 (rem 206 40))) 
(gcd (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40))))
(gcd (rem (rem 206 40) (rem 40 (rem 206 40))) (rem (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40))))) 
(rem (rem 206 40) (rem 40 (rem 206 40))) ;; we have finished this fastly growing expansion and now reduction phase begins
(rem 6 (rem 40 (rem 206 40)))
(rem 6 (rem 40 6))
(rem 6 4)
2

So, generally we need to evaluate (remainder x y) 25 times = 14 times in if condition + 11 times in reduction phase.

Let's compare with applicative evaluation order:

(gcd 206 40)
(gcd 40 6)
(gcd 6 4)
(gcd 4 2)
(gcd 2 0)
2

Here remainder is evaluated only 4 times = one time per each step, except last one.

Exercise1-19 <---> Exercise1-21

Comments

Вапще-то при использовании модели call-by-need (как в Хаскелле, например) количество вычислений rem должно быть не больше, чем при аппликативном порядке вычислений...

Posted by Geniepro at 2007-09-15 02:53:21

Я так понимаю, что call-by-need в Хаскелле и "normal evaluation order" из СИКПа - вещи немного разные. [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html#%_toc_%_sec_Temp_22 Здесь] вот сказано такое: This gives the same answer as our previous evaluation model, but the process is different. In particular, the evaluations of (+ 5 1) and (* 5 2) are each performed twice here, corresponding to the reduction of the expression (* x x). То есть подразумевается, что при нормальном порядке вычисления: (define (square x) (* x x)) (square (+ 2 3)) (* (+ 2 3) (+ 2 3)) (* 5 (+ 2 3)) (* 5 5) 25 Выражение (+ 2 3) вычислится дважды безо всяких оптимизаций.

Posted by IvanVeselov at 2007-09-15 03:13:41

Да, в SICP имеется в виду модель нормального порядка call-by-name, а не call-by-need. ЗЫ. Кстати, если алгоритм является вычислимым, то в случае нормального порядка он в любом случае будет вычислен, тогда как при аппликативном порядке (call-by-value) он может и зациклиться

Posted by Geniepro at 2007-09-15 12:46:49

I believe the answer should be 18 (14 in condition and 4 in reduction). In fact when: rem (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40)))) evaluated to 0 a at that time is (rem (rem 206 40) (rem 40 (rem 206 40)))) is evaluated to 2, then it is the answer returned all the way through without any further evaluation.

Posted by zlee at 2008-01-15 23:32:34 X

Add your comment Markup