男児テストは、コンピュータ科学者ドナルド・クヌースによって、 ALGOL 60プログラミング言語の実装を評価する手段として提案されました。このテストの目的は、 「再帰と非局所参照」を正しく実装したコンパイラとそうでないコンパイラを区別することでした。[ 1]
再帰や非局所参照を適切に処理するように設計されたALGOL60トランスレータは数多く存在します。そこで、ちょっとしたテストプログラムが役に立つかもしれないと考えました。そこで、以下の簡単なルーチンを作成しました。このルーチンによって、manコンパイラとboyコンパイラを区別できるかもしれません。
— ドナルド・クヌース[2]
クヌースの例
ALGOL 60では:
begin
real procedure A ( k , x1 , x2 , x3 , x4 , x5 ) ;値k ;整数k ;実数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
これにより、 B呼び出しフレームのツリーが作成されます。これらのフレームは互いに参照し、また包含するA呼び出しフレームも参照します。各フレームは、対応するBが呼び出されるたびに変化するkのコピーを保持します。紙の上で計算するのはおそらく無駄でしょうが、k = 10の場合、正解は-67です。これは、元の論文ではKnuthが-121と推測していたにもかかわらずです。現代のマシンでさえ、kの値が大きいとすぐにスタック領域が不足します。kの値が大きいほど、スタック領域はすぐに不足します。これは以下の表に示されています（OEIS：A132343）。
| け | |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 2 | −2 |
| 3 | 0 |
| 4 | 1 |
| 5 | 0 |
| 6 | 1 |
| 7 | −1 |
| 8 | −10 |
| 9 | −30 |
| 10 | −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 |
説明
このプログラムで使用されている 3 つの Algol 機能は、コンパイラで適切に実装するのが難しい場合があります。
- ネストされた関数定義： B はAのローカルコンテキストで定義されているため、 Bの本体はAのローカルなシンボルにアクセスできます。特にkは B によって変更されますが、 x1、 x2、、 x4、 x5もアクセスできます。これは Algol の派生言語であるPascalでは簡単ですが、もう一つの主要な Algol の派生言語であるCでは不可能です（C の address-of 演算子を用いて手動でメカニズムをシミュレートし、関数間でローカル変数へのポインタを渡す必要があります）。
- 関数参照：再帰呼び出しにおけるBはB
A(k, B, x1, x2, x3, x4)への呼び出しではなく、 Bへの参照です。B はk が0より大きい場合にのみ呼び出されます。これは標準Pascal（ ISO 7185）およびC言語では簡単です。Pascalの一部の派生言語（例えば、 Turbo Pascalの旧バージョン）は手続き参照をサポートしていませんが、参照される可能性のある関数の集合が事前にわかっている場合（このプログラムではBのみ）、この問題を回避できます。 - 定数/関数の二重性: Aのx1からx5までのパラメータは、数値定数または関数Bへの参照である可能性があります。式は、仮パラメータx4とx5が対応する実パラメータ（名前による呼び出し）に置き換えられたかのように、両方のケースを処理できるように準備する必要があります。 [3]これは、動的型付け言語よりも静的型付け言語で問題になる可能性が高いですが、標準的な回避策は、 Aへのメイン呼び出しで定数1、0、および-1を、これらの値を返す引数のない関数として再解釈することです。
x4 + x5
しかし、これらはテストの本質ではありません。テストが意味を持つための前提条件に過ぎません。テストの目的は、Bへの異なる参照が、 Bの正しいインスタンス、つまり参照を作成したBと同じAローカルシンボルにアクセスできるインスタンスに解決されるかどうかです。例えば、「少年」コンパイラは、 Bが常に最上位のA呼び出しフレームにアクセスするようにプログラムをコンパイルするかもしれません。
参照
参考文献
- ^ Ardö, Anders; Philipson, Lars (1984年3月). 「A simple Ada compiler invalidation test」. ACM SIGAda Ada Letters . III (5): 69– 74. doi : 10.1145/998382.998385 . ISSN 1094-3641.
- ^ ドナルド・クヌース (1964年7月). 「男か少年か?」ALGOL Bulletin . 17 : 7. 「AB17.2.4 ドナルド・クヌース：男か少年か？ 7ページ」。archive.computerhistory.org。 参照：「Algol Bulletin」。Chiltonにおけるコンピューティング：1961～2000年。 2009年12月25日閲覧。
- ^ Wichmann, BA (1972-02-01). 「5つのALGOLコンパイラ」 .コンピュータジャーナル. 15 (1): 8. doi :10.1093/comjnl/15.1.8. ISSN 0010-4620.
外部リンク
- 多くのプログラミング言語における男性または少年のテスト例
