Как работает тест Кнута "Мужчина или мальчик"?

Question

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

Answer 1

Это хорошая страница в этом тесте "Человек или мальчик". Здесь показаны следующие интересные факты:

k = 10: A = -67 и A вызывается 722 раза, B вызывается (A - 1) раз.

Написание полной calltrace в этом случае немного бесполезно, так как функция рекурсивна по своей природе, с добавлением, что функции не чисты (как вы можете видеть в переводе на Haskell, она требует использования монад STate, обернутых вокруг 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, некоторые реализации были неправильными. Тест был сделан, чтобы отделить неправильные реализации от тех, которые являются правильными.