Бесконечная рекурсия, когда `если` переопределено, почему?

Question

Я новичок в программировании и начал изучать языковую схему.(Я изучаю книгу «Структура и интерпретация компьютерных программ»), и мне попалась одна задача, которая описана ниже.Я написал два кода, заменив if на cond, но по какой-то причине при запуске первого кода возникает бесконечная рекурсия, но при запуске второго кода бесконечной рекурсии нет, и обычно он вычисляет sqrt .... хотя код такой же, почему это так?

Алисса П. Хакер не понимает, почему if необходимо предоставить в виде специальной формы.«Почему я не могу просто определить это как обычную процедуру в терминах cond?» - спрашивает она.Подруга Алиссы, Ева Лу Атор, утверждает, что это действительно возможно, и она определяет новую версию if:

(define (new-if predicate then-clause else-clause)
    (cond (predicate then-clause)
        (else else-clause)))

Ева демонстрирует программу для Алиссы:

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

В восторге, Алисса использует new-if для перезаписи программы square-root:

(define (sqrt-iter guess x)
    (new-if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x)
        x)))

Что происходит, когда Алисса пытается использовать это для вычисленияквадратные корни?Объясните.

Первый код:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (square x)
  (* x x))

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (better-good-enough? prev-guess guess)
  (< (abs (- guess prev-guess))
     0.00001))

(define (better-sqrt-iter prev-guess guess x)
  (new-if (better-good-enough? prev-guess guess)
      guess
      (better-sqrt-iter guess
                        (improve guess x)
                        x)))

(define (better-sqrt x)
  (better-sqrt-iter 0 1.0 x))

Второй код:

(define (square x)
  (* x x))

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (better-good-enough? prev-guess guess)
  (< (abs (- guess prev-guess))
     0.00001))

(define (better-sqrt-iter prev-guess guess x)
  (cond ((better-good-enough? prev-guess guess)
      guess)
        (else (better-sqrt-iter guess
                        (improve guess x)
                        x))))

(define (better-sqrt x)
  (better-sqrt-iter 0 1.0 x))

Answer 1

Это пахнет домашним заданием, но, если вы используете Схему, подумайте, что происходит, когда общая форма (а не какая-либо специальная форма) похожа на

(f a b c)

оценивается:

1. f, a, b & c оцениваются в некотором неопределенном порядке (возможно, даже сразу);
2. Значение f (результат его оценки другими словами), которое должно быть функцией, применяется к результатам оценки a, b & c;
3. Функция возвращает значение (или значения), и это значение формы.

Что происходит, когда вы используете эту стратегию оценки, чтобы попытаться оценить первую версию better-sqrt-iter? Вы можете просто выполнить некоторые оценки вручную, используя бумагу и карандаш, чтобы увидеть, что произойдет.

Почему это правило оценки здесь проблема?

Answer 2

Мы можем использовать модель замещения.

(better-sqrt 1) 
(better-sqrt-iter 0 1.0 1)
(cond
  ((better-good-enough? 0 1.0) 1.0)
  (else
   (better-sqrt-iter 1.0
                     (improve 1.0 1)
                     1))))
(cond
  (#f 1.0)
  (else
   (better-sqrt-iter 1.0
                     (improve 1.0 1)
                     1))))

(better-sqrt-iter 1.0
                  (improve 1.0 1)
                  1)
(better-sqrt-iter 1.0
                  1.0
                  1)
(cond
  ((better-good-enough? 1.0 1.0) 1.0)
  (else
   (better-sqrt-iter 1.0
                     (improve 1.0 1.0)
                     1))))
(cond
  (#t 1.0)
  (else
   (better-sqrt-iter 1.0
                     (improve 1.0 1.0)
                     1))))
1.0

Теперь давайте попробуем то же самое с new-if:

(better-sqrt 1) 
(better-sqrt-iter 0 1.0 1)

Схема говорит, что вы можете оценивать процедуры в любом порядке.Я выбираю справа налево!

(new-if (better-good-enough? 0 1.0) 
        1.0
        (better-sqrt-iter 1.0
                          (improve 1.0 1)
                          1))
(new-if (better-good-enough? 0 1.0) 
        1.0
        (new-if (better-good-enough? 1.0 1.0) 
                1.0
                (better-sqrt-iter 1.0
                                  (improve 1.0 1)
                                  1)))
(new-if (better-good-enough? 0 1.0) 
        1.0
        (new-if (better-good-enough? 1.0 1.0) 
                1.0
                (new-if (better-good-enough? 1.0 1.0) 
                        1.0
                        (better-sqrt-iter 1.0
                                          (improve 1.0 1)
                                          1))))
(new-if (better-good-enough? 0 1.0) 
        1.0
        (new-if (better-good-enough? 1.0 1.0) 
                1.0
                (new-if (better-good-enough? 1.0 1.0) 
                        1.0
                        (new-if (better-good-enough? 1.0 1.0) 
                                1.0
                                (better-sqrt-iter 1.0
                                                  (improve 1.0 1)
                                                  1)))))
;; goes on like this forever!

Обратите внимание, что мне никогда не удается выполнить ни один из вызовов good-enough, поскольку все 3 выражения необходимо завершить до тела new-if может быть вычислено, тогда как встроенный if сначала оценивает тестовое выражение, а затем оценивает только одно из последующего или альтернативного выражения, основываясь на результате оценки тестового выражения, иТаким образом, рекурсия останавливается.