Как работает тест Кнута «Человек или мальчик»?

Question

Может ли кто-нибудь объяснить, как Man Or Boy Test возвращает значение -67?
Я тщетно пытался записать результат или отследить его с помощью отладчика. Любая помощь будет оценена по достоинству.
Список различных реализаций можно найти here.

Answer 1

This is a nice page Об этом человеке или мальчике. Здесь показаны следующие интересные факты:

k = 10: A = -67, а A - 722 раз, B - (A - 1) раз.

Дать полный calltrace немного бесполезный в данном случае, так как функция в природе рекурсивный, с тем дополнением, что эти функции не являются чисто (как вы можете видеть в переводе на Haskell, она требует использование STATE Monads, завернутое вокруг k, чтобы сохранить примесь): область каждой функции (в этом случае переменная k: она уменьшена на единицу) изменяется каждый вызов или рекурсия, и эти изменения необходимы для расчета правильного ответа ,

Я нахожу перевод JavaScript немного более удобным для чтения, чем первоначальная реализация ALGOL60:

function A(k, x1, x2, x3, x4, x5) { 
    function B() { 
     return A(--k, B, x1, x2, x3, x4); 
    } 
    return k <= 0 ? x4() + x5() : B(); 
} 
function K(n) { return function() {return n}; } 
alert(A(10, K(1), K(-1), K(-1), K(1), K(0))); 

Хитрость заключается в том бухучет: какие ссылки на функции вызывают которые побочные эффекты (модификация переменных) и в перспективе дела правильная оценка функции. Однако эта бухгалтерия является утомительной, как я объяснил ранее.

Современные языки, такие как этот пример JavaScript, имеют правильные интерпретаторы/компиляторы для обработки этих случаев бухгалтерского учета. Были составлены компиляторы времени ALGOL60, некоторые из реализаций были неправильными. Был проведен тест, чтобы отделить неправильные реализации от правильных.