Prueba de hombre o niño

La prueba del "hombre o niño" fue propuesta por el científico informático Donald Knuth como un método para evaluar las implementaciones del lenguaje de programación ALGOL 60. El objetivo de la prueba era distinguir los compiladores que implementaban correctamente la " recursión y las referencias no locales " de aquellos que no lo hacían. ^{[ 1 ]}

Existen varios traductores de ALGOL60 diseñados para manejar correctamente la recursión y las referencias no locales, y pensé que un pequeño programa de prueba podría ser útil. Por lo tanto, he escrito la siguiente rutina sencilla, que puede ayudar a distinguir a los compiladores expertos de los principiantes.

En ALGOL 60 :

begin real procedure A ( k , x1 , x2 , x3 , x4 , x5 ) ; value k ; integer k ; real x1 , x2 , x3 , x4 , x5 ; begin real procedure B ; begin k := k - 1 ; B := A := A ( k , B , x1 , x2 , x3 , x4 ) end ; if k ≤ 0 then A := x4 + x5 else B end ; outreal ( 1 , A ( 10 , 1 , - 1 , - 1 , 1 , 0 )) end

Esto crea un árbol de marcos de llamada B que se refieren entre sí y a los marcos de llamada A que los contienen , cada uno de los cuales tiene su propia copia de k que cambia cada vez que se llama al B asociado . Intentar resolverlo en papel probablemente sea inútil, pero para k  =  10, la respuesta correcta es −67, a pesar de que en el artículo original Knuth conjeturó que era −121. Incluso las máquinas modernas se quedan rápidamente sin espacio de pila para valores mayores de k , que se tabulan a continuación ( OEIS : A132343  ).

En este programa se utilizan tres características de Algol que pueden ser difíciles de implementar correctamente en un compilador:

1. Definiciones de funciones anidadas : Dado que B se define en el contexto local de A , el cuerpo de B tiene acceso a símbolos que son locales a A , principalmente k , al que modifica, pero también x1 , x2 , x3 , x4 y x5 . Esto es sencillo en Pascal , descendiente de Algol, pero no es posible en C , el otro descendiente principal de Algol(sin simular manualmente el mecanismo usando el operador de dirección de C, pasando punteros a variables locales entre las funciones).
2. Referencias a funciones : La B en la llamada recursivaA(k, B, x1, x2, x3, x4)no es una llamada a B , sino una referencia a B , que se llamará solo cuando k sea mayor que cero. Esto es sencillo en Pascal estándar ( ISO 7185 ) y también en C. Algunas variantes de Pascal (por ejemplo, versiones antiguas de Turbo Pascal ) no admiten referencias a procedimientos, pero cuando se conoce de antemano el conjunto de funciones a las que se puede hacer referencia (en este programa solo es B ), esto se puede solucionar.
3. Dualismo constante/función : Los parámetros x1 a x5 de A pueden ser constantes numéricas o referencias a la función B ; la x4 + x5expresión debe estar preparada para manejar ambos casos como si los parámetros formales x4 y x5 hubieran sido reemplazados por el parámetro real correspondiente ( llamada por nombre ). ^{[ 3 ]} Esto probablemente sea un problema mayor en lenguajes de tipado estático que en lenguajes de tipado dinámico, pero la solución estándar es reinterpretar las constantes 1, 0 y -1 en la llamada principal a A como funciones sin argumentos que devuelven estos valores.

Sin embargo, estos aspectos no constituyen el objetivo de la prueba; son simplemente requisitos previos para que la prueba tenga algún sentido. La prueba consiste en determinar si las diferentes referencias a B se resuelven en la instancia correcta de B , es decir, una que tenga acceso a los mismos símbolos locales de A que la instancia de B que creó la referencia. Un compilador "boy" podría, por ejemplo, compilar el programa de forma que B siempre acceda al marco de llamada de A de nivel superior .

• Problema de Funarg
• El dispositivo de Jensen

• Ejemplos de pruebas para hombres o niños en muchos lenguajes de programación