Test homme ou garçon - Man or boy test

Le test homme ou garçon a été proposé par l'informaticien Donald Knuth comme moyen d'évaluer les implémentations du langage de programmation ALGOL 60 . Le but du test était de distinguer les compilateurs qui implémentaient correctement les « références récursives et non locales » de ceux qui ne le faisaient pas.

Il existe pas mal de traducteurs ALGOL60 qui ont été conçus pour gérer correctement la récursivité et les références non locales, et j'ai pensé qu'un petit programme de test pourrait être utile. C'est pourquoi j'ai écrit la routine simple suivante, qui peut séparer les compilateurs man des compilateurs garçons.

-  Donald Knuth

L'exemple de Knuth

Dans 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(A(10, 1, -1, -1, 1, 0))
end;

Cela crée un arbre de trames d'appel B qui se réfèrent les unes aux autres et aux trames d'appel A contenant , chacune ayant sa propre copie de k qui change à chaque fois que le B associé est appelé. Essayer de le travailler sur papier est probablement infructueux, mais pour k  = 10, la bonne réponse est −67, malgré le fait que dans l'article original, Knuth l'a supposé être −121. L'article d'enquête de Charles H. Lindsey mentionné dans les références contient un tableau pour différentes valeurs de départ. Même les machines modernes manquent rapidement d' espace de pile pour des valeurs plus élevées de k , qui sont présentées ci-dessous ( OEIS :  A132343 ).

k
0 1
1 0
2 −2
3 0
4 1
5 0
6 1
7 −1
8 −10
9 −30
dix −67
11 −138
12 −291
13 −642
14 −1446
15 −3250
16 −7244
17 −16 065
18 −35 601
19 −78 985
20 −175 416
21 −389 695
22 −865 609
23 −1 922 362
24 −4 268 854
25 −9 479 595
26 −21 051 458

Explication

Il y a trois fonctionnalités Algol utilisées dans ce programme qui peuvent être difficiles à implémenter correctement dans un compilateur:

  1. Définitions de fonctions imbriquées : Puisque B est défini dans le contexte local de A , le corps de B a accès aux symboles qui sont locaux à A - notamment k , qu'il modifie, mais aussi x1 , x2 , x3 , x4 et x5 . C'est simple dans le descendant d'Algol Pascal , mais pas possible dans l'autre grand descendant d'Algol C (sans simuler manuellement le mécanisme en utilisant l'opérateur d'adresse de C, en passant des pointeurs vers des variables locales entre les fonctions).
  2. Références de fonction : Le B dans l'appel récursif A(k, B, x1, x2, x3, x4) n'est pas un appel à B , mais une référence à B , qui ne sera appelée que lorsque k est supérieur à zéro. C'est simple en Pascal standard ( ISO 7185 ), mais aussi en C. Certaines variantes de Pascal (par exemple les anciennes versions de Turbo Pascal ) ne prennent pas en charge les références de procédure, mais lorsque l'ensemble des fonctions pouvant être référencées est connu à l'avance (dans ce programme ce n'est que B ), cela peut être contourné.
  3. Dualisme constante / fonction : Les paramètres x1 à x5 de A peuvent être des constantes numériques ou des références à la fonction B - l' x4 + x5 expression doit être préparée pour gérer les deux cas comme si les paramètres formels x4 et x5 avaient été remplacés par le paramètre réel correspondant ( appel par nom ). C'est probablement plus un problème dans les langages à typage statique que dans les langages à typage dynamique, mais la solution de contournement standard consiste à réinterpréter les constantes 1, 0 et -1 dans l'appel principal à A comme des fonctions sans arguments qui renvoient ces valeurs.

Ces choses ne sont cependant pas l'objet du test; ce ne sont que des conditions préalables pour que le test ait un sens. Le test consiste à déterminer si les différentes références à B se résolvent en l' instance correcte de B - celle qui a accès aux mêmes symboles A -local que le B qui a créé la référence. Un compilateur "garçon" pourrait, par exemple, à la place compiler le programme de sorte que B accède toujours à la trame d'appel A la plus haute .

Voir également

Les références

Liens externes