Аппликативный и нормальный порядки вычисления

evaluate-model.lisp

; Аппликативный и нормальный порядки вычисления
;
; «полная подстановка, затем редукция» известен под на-
; званием нормальный порядок вычислений (normal-order evaluation)
;
; Пример работы нормального порядка вычисления
; Последовательность подстановок
;     (sum-of-squares (+ 5 1) (* 5 2))
;     (+ (square (+ 5 1)) (square (* 5 2))
;     (+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
;
; за которыми последуют редукции
;     (+ (* 6 6) (* 10 10))
;     (+ 36 100)
;
; вычисление (+ 5 1) и (* 5 2) выполняется
; здесь по два раза, в соответствии с редукцией выражения
;
; «вычисление аргументов, затем применение процедуры», кото-
; рое называется аппликативным порядком вычислений (applicative-order evaluation)
;
; Пример работы аппликативного порядка вычисления
;     (sum-of-squares (+ 5 1) (* 5 2))
;     (+ (square 6) (square 10))
;     (+ 36 100)
;
; Тест Бена Битбора для проверки интерпретатора
; на то, с каким порядком вычислений он работает , аппликативным или нормальным

(define (p) (p))
(define (test x y)
  (if (= x 0)
      0
      y))

(test 0 (p))

; В случае аппликативного порядка вычисления мы не войдем в процедуру test
; так-как не сможем вычислить рекурсивную процедуру p

Большое спасибо за пример

отличное объфснение! спасибо большое)))

спасибо за пример

Спасибо, в книге и в правду запутанно дано

Спасибо, помогло

Спасибо, теперь понял!)

https://codology.net/post/sicp-solution-exercise-1-5/

Вот тут ещё более понятный ответ.

Я так понял, что "нормальный" порядок вычисления корректней называть "ленивым". Потому что, в случае аппликативного порядка (p) будет вычисляться ещё до запуска процедуры test, и потому мы попадёт в бесконечный луп (потому что (p) ссылается на саму себя). В случае "нормального" или "ленивого" порядка интерпретатор не дойдёт до вычисления (p), так как он сначала проверит что 0 = 0 и просто вернёт 0 -- он не дойдёт до вычисления (p) и не попадёт в луп. Вроде так.