Решение упражнения 1.6 из SICP
Отличное упражнение на понимание того, как происходит выполнение процедур.
Вспомним прошлое упражнение и тот факт, что Scheme при интерпретации использует аппликативный порядок вычислений. Итак, как же будет вычисляться фунция Лизы?
(define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))
При вычислении new-if сначала должны быть вычислены все ее аргументы. С первыми двумя из них проблем нет, а вот при вычислении третьего new-if снова обращается к sqrt-iter, которая затем опять вызовет new-if… и так до бесконечности. Ограничивающего условия, обеспечивающего выход из этого порочного круга, нет. Таким образом программа Лизы, переписанная в таком виде, зациклится.
Почему же такой проблемы не возникает при использовании нормального if вместо new-if? Все просто. Обычный if является особой формой, он вычисляется не так, как стандартные процедуры. Для вычисления его значения не обязательно будут вычислены все операнды (более того, гарантированно будут вычислены только два из трех). Таким образом sqrt-iter будет вычисляться только в случае, когда решение еще не достаточно хорошее, а в противном случае вычисляться не будет, что и гарантирует выход из цикла.
Comments
Comment from Игорь
Date: October 21, 2011, 4:10 pm
Пример был проверен на Racket v5.1.3. Процедура отрабатывает результат и возвращает корректное значение. Думаю, что правильный ответ на задачу 1.6 - “Процедура отработает нормально”. Дело в том, что в условном выражении cond все предикаты вычисляются поочереди, условие else не будет вычисляться если p1 true.
стр 15 книги: “… Условные выражения вычисляются так: сначала вычисляется предикат . Если его значением является ложь, вычисляется ….
Comment from Андрей
Date: November 1, 2011, 2:23 pm
тоже проверял на Racket v5.1.3 - зацикливается
Comment from Антон Платонов
Date: November 2, 2011, 2:10 am
Игорь, я тоже тут проверил в Racket v5.1.3, и у меня зацикливается интерпретатор.
Comment from Руслан
Date: November 4, 2011, 9:24 pm
to Игорь:
Тут дело в том, что при вызове процедуры new-if, вначале вычисляются операнды, а только потом применяется оператор (в данном случае - процедура new-if, с в теле которого находится cond), и поэтому второй операнд будет вызываться бесконечно.
Упражнение проверено на DrRacket v. 5.1.3, результат - бесконечный луп, по причине, описанной выше.
Comment from Егор
Date: January 6, 2012, 1:16 pm
Я проверил на MIT/GNU Scheme версии 9.1. Результат вот какой:
;Aborting!: maximum recursion depth exceeded
Cond действительно вычисляет предикаты и выражения по мере необходимости, дело не в этом.
Дело в том, что при аппликативном порядке вычисления комбинация (sqrt-iter (improve guess x) x) будет вычислена до того, как будет начато вычисление комбинации new-if. В результате до вычисления cond внутри new-if’а дело вообще не доходит, получается бесконечная рекурсия sqrt-iter.
А Racket, видимо, использует нормальный порядок вычисления.
Учитывая, что в SICP используется scheme, я думаю, правильный ответ — при аппликативном порядке вычисления произойдет зацикливание 
Comment from Валерий
Date: January 12, 2012, 1:47 am
Все-таки товарищ Игорь неправ.
Скорее всего он заменил if на cond прямо в теле sqrt-iter, что делать можно т.к. и то и другое особые формы и к ним неприменяется апликативный порядок вычислений.
Если же обернуть cond в new-if (как и сказано в книге) то т.к. у new-if и у if разный порядок вычислений то будет зацикливание.(проверил пример на Racket v5.2).
p.s. Я для себя принял такое упрощенное описание этого “апликативного порядка вычислений” - все описаные функции будут вызванны.
Таким образом для реализации рекурсии нужны доп средства(особые формы типа if) - на чем и основана идея проверки порядка вычислений из упражнения 1.5
Comment from Дмитрий
Date: January 14, 2012, 11:15 pm
Да, действительно в Racket работает. Проверял на версии 5.2. Но это очень странно, так как программа должна зацикливаться при вызове процедуры new-if.
Игорь, условные выражения здесь ни при чём. Программа должна зацикливаться при вызове процедуры new-if. Почему она этого не делает - для меня загадка.
Comment from Юра
Date: January 21, 2012, 2:15 pm
Есть предположение, что Racket не так прост, как кажется. Например, у вас может получаться разный результат, если у вас по-разному настроен сам Racket. Есть подоздение, что кто-то из участников обсуждения включил Lazy Racket и поэтому у него все вычисляется.
Я только что проверил, если в исходнике объявить язык как #lang racket то все циклится, т.к. используется традиционные аппликативный порядок вычисления. А вот если объявить язык как #lang lazy - то работает, т.к. здесь очевидно используются ленивые вычисления.
В общем, чтобы не было дальше таких расхождений рекомендую всегда указывать используемый язык при помощи директивы #lang и включить опцию “Use language declared in the source”
Write a comment