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

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