Решение упражнения 1.6 из SICP

15 August, 2007 (20:49) | Решения упражнений

Отличное упражнение на понимание того, как происходит выполнение процедур.

Вспомним прошлое упражнение и тот факт, что 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”

Comment from Александр
Date: July 23, 2012, 3:41 pm

Скорее всего дело в настройке racket. В нем можно выбрать язык или задать директивой #lang. Я использую #lang scheme, зацикливание происходит. Версия 5.2.1

Comment from Денис
Date: September 11, 2012, 10:54 pm

Не совсем понятно. Если используется нормальный порядок вычислений то “ложная” ветка не должна вычисляться. При использовании if должен быть нормальный порядок, однако, если взять пример из предыдущего упражнения (1.5) интерпретатор все равно уходит в бесконечную рекурсию, хотя, по идее, должно вычисляться выражение только “верной” ветки, которая возвращает 0.

Comment from Владимир
Date: November 28, 2012, 6:12 pm

На tinyscheme приложение завершилось с ошибкой “no memory”, или что-то подобное, свидетельствующее о том, что были исчерпаны ресурсы.

Comment from Вячеслав
Date: April 19, 2013, 9:32 am

Привет! Подскажите такую вещь, если в упражнении 1.5 с нормальным if происходит “зацикливание” – значит порядок аппликативный, так? Тогда и в этой программе с нормальным if должно оно происходить, но выполняется нормально.
(все выполняю на CL, sbcl)

Comment from filimon
Date: April 27, 2013, 2:57 pm

to Вячеслав:
Странно.. я тоже проверял на sbcl.. результат вот такой: Control stack guard page temporarily disabled: proceed with caution

Comment from freecode
Date: May 11, 2013, 8:35 am

В упражнении 1.5 сначала вычисляются аргументы процедуры (test x y), где и происходит зацикливание.

Comment from ghost
Date: August 31, 2013, 1:14 pm

а по-моему зацикливание произойдет из-за первого аргумента процедуры new-if

Comment from Виктор
Date: November 10, 2014, 5:13 pm

Racket 6.1.1
Включен режим “Начинающий студент”, никаких #lang, функции abs и square переименованы и взяты из книги.
Всё работает как задумано автором книги, то есть бесконечная рекурсия функции sqrt-iter.

Comment from malkinfedor
Date: March 19, 2015, 10:06 pm

При выполнении следующего кода становится наглядно видно, что при функции if вычисляется предикат, и если он возвращает значение true то вычисляется только следствие, альтернатива не вычисляется

(define(sqrt-iter guess x)
  (if (= 0 0) guess (sqrt-iter(improve guess x) x)))

(sqrt-iter 2 1)

функция sqrt-iter вернет в любом случае значение guess (2), так как предикат возвращает true.

Если поменять значение предиката на такое, что бы он возвращал false (например (= 0 1)), то функция замкнется и не будет выполнена никогда, так как никогда не будет достигнуто равенство 0 и 1.
Отсюда следует вывод, что if считает только значение следствия, и не считает значения альтернативы, если оно не требуется. Применительно к примеру 1.7 понятно, что в конце концов будет достигнуто условие, когда предикат вернет true, и альтернатива считаться не будет.

Если же мы попробуем тот же код переписать под использование функции new-if, то происходит замыкание функции, так как она всегда будет высчитывать и значение (sqrt-iter (improve guess x) x), что само по себе превращает функцию sqrt-iter в замкнутую, и действительно, до вычисления cond не дойдет.

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

Comment from Мария
Date: September 23, 2017, 9:44 am

Странно, что в книге изначально не даны правильные ответы где-нибудь в конце, как это обычно бывает? Как убедиться, что материал усвоен верно, если сравнивать приходится с ответами таких же студентов 🙂

И ещё один вопрос. Если в предыдущем задании про (test 0 y) программа ничего не выдаёт, это означает, что она зациклилась? Значит, мой интерпретатор вычисляет аппликативным методом? Хоть бы что-то написал в ответ. А то тишина, никаких надписей и ругани, как это бывает при ошибках.

Comment from Мария
Date: September 29, 2017, 10:08 am

Разобралась со своим DrRacket. Версия 6.10.1. Программа обрадованной Лизы с new-if зацикливается. Потому что Лиза использовала составную процедуру new-if, которую определила её подруга Ева с помощью формы cond. А cond будет выполнять условия последовательно до тех пор, пока не найдёт истину, а иначе вернёт else. Но т.к. Лиза в else записала sqrt-iter, для определения которого Лиза использует тот же new-if, то образуется бесконечный запрос от new-if к sqrt-iter и от sqrt-iter к new-if. Поэтому программа не может быть выполнена.
Интерпретатор выдаёт:
Interactions disabled

Write a comment