Haskell аппликативный или нормальный?

#haskell #sicp

Я изучаю язык Haskell и параллельно читаю SICP. В SICP нашёл следующее.
Бен Битобор (согласно книге SICP) придумал тест для проверки интерпретатора на то,
с каким порядком вычислений он работает, аппликативным или нормальным. Бен определяет
такие две процедуры:

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


Затем он вычисляет выражение:

(test 0 (p))


Если результатом является 0, то интерпретатор - нормальный, если впадает в вычисление
"p" - аппликативный. Согласно теста язык Scheme является аппликативным.
Я переписал проверку под Haskell для интерпретатора GHCi:

let p = p
let test x y = if (x == 0) then 0 else y
test 0 p


Результатом получил 0.
Правильно ли я применил тест Битобора, результатом которого является факт, что Haskell
(GHCi) является нормальным языком программирования? Равносильно ли это понятию "ленивые
вычисления"?
    

Ответы

Ответ 1

Всё правильно

Да, Haskell в терминах этой книги нормальный.

...и речь действительно идёт о ленивых вычислениях, а именно ленивом вычислении аргументов
функции при её вызове. Термина нормальный стоит в этом контексте избегать ввиду его
излишней общности и распространённости в самых разных областях, термин ленивый куда
осмысленнее.

Первая процедура — очевидная "рекурсивная бомба", которая вешает выполнение программы
при попытке вызова (если нет оптимизации хвостовой рекурсии, то ещё и уронит программу).
Поэтому весь тест упирается в то, будет ли вычислен второй аргумент независимо от того,
потребует ли его значения функция в процессе выполнения.

Внимание стоит обратить лишь на ту деталь, что нельзя просто так выкинуть вторую
процедуру и заинлайнить её вызов в её реализации как-то так:

(if (= 0 0) 0 (p))


...потому что if в лиспах обычно является особой формой (special form), а не функцией,
а потому имеет другой порядок вычислений, чем для вызовов функций.