Skip to content

Instantly share code, notes, and snippets.

@maksimr
Created March 21, 2014 14:09
Show Gist options
  • Save maksimr/9687065 to your computer and use it in GitHub Desktop.
Save maksimr/9687065 to your computer and use it in GitHub Desktop.
Аппликативный и нормальный порядки вычисления
; Аппликативный и нормальный порядки вычисления
;
; «полная подстановка, затем редукция» известен под на-
; званием нормальный порядок вычислений (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
@RobertV17
Copy link

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

@TrashPanda626
Copy link

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

@DmitriBarannyk
Copy link

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

@skhrv
Copy link

skhrv commented Aug 3, 2019

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

@AlexMold
Copy link

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

Copy link

ghost commented Jan 13, 2020

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

@tampambro
Copy link

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

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

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment