¿Cómo funciona la prueba Knuth "Man or Boy"?

Question

¿Alguien puede explicar cómo el Man Or Boy Test devuelve un valor de -67?
Intenté en vano escribir el resultado, o rastrearlo con un depurador. Cualquier ayuda sería apreciada.
Se puede encontrar una lista de las diferentes implementaciones here.

Answer 1

This is a nice page en esta prueba de Hombre o Chico. Muestra los siguientes hechos interesantes:

k = 10: A = -67 y A se llama 722 veces, B se llama (A - 1) veces.

Escribir un calltrace completa es un poco inútil en este caso, ya que la función es recursiva en la naturaleza, con la particularidad de que las funciones no están pura (como se puede ver en la traducción Haskell, se requiere la uso de STate Monads, envuelto alrededor de k, para mantener la impureza lejos): el alcance de cada función (en este caso la variable k: se reduce en uno) se modifica cada llamada o recursión y estas modificaciones son necesarias para el cálculo de la respuesta correcta .

se encuentra la traducción de JavaScript un poco más fácil de leer, que la aplicación ALGOL60 el original:

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))); 

El truco está en la contabilidad: lo que las referencias a las funciones causa que los efectos secundarios (modificación de variables) y en la causa plazo una evaluación de función correcta. Sin embargo, esta contabilidad es tediosa, como expliqué anteriormente.

Los idiomas modernos, como este ejemplo de JavaScript, tienen intérpretes/compiladores correctos para manejar estos casos de contabilidad. La vez que se hicieron los compiladores ALGOL60, algunas de las implementaciones no eran correctas. La prueba se realizó para separar las implementaciones incorrectas de las correctas.