Это хорошая страница об этом тесте для мужчины или мальчика. Здесь показаны следующие интересные факты:
k = 10: A = -67 и A вызывается 722 раза, B вызывается (A - 1) раз.
Запись полной calltrace в этом случае немного бесполезна, так как функция рекурсивная по своей природе, с добавлением, что функции не pure (как вы можете видеть в в переводе на 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, некоторые реализации были неправильными. Тест был сделан, чтобы отделить неверные реализации от правильных.