Упражнение из SICP
Michael N. Kuleshov
Добрый день, All!
В SICP на с. 39 приведено такое упражнение:
======================================================================
Упражнение 1.5.
Бен Битобор придумал тест для проверки интерпретатора на то, с каким
порядком вычислений он
работает, аппликативным или нормальным. Бен определяет такие две процедуры:
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
Затем он вычисляет выражение
(test 0 (p))
Какое поведение увидит Бен, если интерпретатор использует аппликативный
порядок вычислений?
Какое поведение он увидит, если интерпретатор использует нормальный
порядок? Объясните Ваш
ответ. (Предполагается, что правило вычисления особой формы if одинаково
независимо от того,
какой порядок вычислений используется. Сначала вычисляется
выражение-предикат, и результат
определяет, нужно ли вычислять выражение-следствие или альтернативу.)
======================================================================
(define (p) (p)) - не понял. Это не именование какой-то величины или
процедуры.
В GNU CLISP ввод (define (p) (p)) вызывает ошибку интерпретатора.
MIT/GNU Scheme пока не разобрался как запускать.
Подскажите, плз.
Пока лишь догадался, что для случая аппликативного метода (?вычисление
аргументов, затем применение процедуры?) (p) будет неопределено (?),
сообщение об ошибке.
А для нормального метода (?полная подстановка, затем редукция?) будет
напечатан 0. Так?
Так что же такое (define (p) (p))?
Михаил
Alexey Desyatnik
MNK> (define (p) (p)) - не понял. Это не именование какой-то величины или
MNK> процедуры.
Бесконечная рекурсия. Скажем, на си это будет так:
int p() { return p(); }
MNK> В GNU CLISP ввод (define (p) (p)) вызывает ошибку интерпретатора.
В Common Lisp вообще нет никакого define, там defun и прочие setf.
MNK> Пока лишь догадался, что для случая аппликативного метода (?вычисление
MNK> аргументов, затем применение процедуры?) (p) будет неопределено (?),
MNK> сообщение об ошибке.
Почти так. Будет зависон.
MNK> А для нормального метода (?полная подстановка, затем редукция?) будет
MNK> напечатан 0. Так?
Совершенно верно.
Alex Mizrahi
MNK> величины или процедуры.
(define (p) (p)) = (define p (lambda () (p)))
так понятнее?
MNK> В GNU CLISP ввод (define (p) (p)) вызывает ошибку
интерпретатора.
логично, учитывая что это не Scheme, а Common Lisp.
там это записывается так:
(defun p () (p))
но, учитывая что Common Lisp не гарантирует оптимизацию хвостовой рекурсии,
вечных цикл более корректно записать так:
(defun p () (loop))