Man or boy test

<h2 id="knuths-example">Knuth's example</h2>
In <a href="/facts/ALGOL_60/QnpxUYQm">ALGOL 60</a>:

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

This creates a tree of B call frames that refer to each other and to the containing A call frames, each of which has its own copy of k that changes every time the associated B is called. Trying to work it through on paper is probably fruitless, but for k = 10, the correct answer is −67, despite the fact that in the original article Knuth conjectured it to be −121. Even modern machines quickly run out of <a href="/facts/Call_stack/1sMt713v">stack</a> space for larger values of k, which are tabulated below (<a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A132343).

<table><tbody><tr><th>k</th><th>⁠ A ( k , 1 , − 1 , − 1 , 1 , 0 ) {\displaystyle A(k,1,-1,-1,1,0)} ⁠</th></tr><tr><td>0</td><td>1</td></tr><tr><td>1</td><td>0</td></tr><tr><td>2</td><td>−2</td></tr><tr><td>3</td><td>0</td></tr><tr><td>4</td><td>1</td></tr><tr><td>5</td><td>0</td></tr><tr><td>6</td><td>1</td></tr><tr><td>7</td><td>−1</td></tr><tr><td>8</td><td>−10</td></tr><tr><td>9</td><td>−30</td></tr><tr><td>10</td><td>−67</td></tr><tr><td>11</td><td>−138</td></tr><tr><td>12</td><td>−291</td></tr><tr><td>13</td><td>−642</td></tr><tr><td>14</td><td>−1446</td></tr><tr><td>15</td><td>−3250</td></tr><tr><td>16</td><td>−7244</td></tr><tr><td>17</td><td>−16065</td></tr><tr><td>18</td><td>−35601</td></tr><tr><td>19</td><td>−78985</td></tr><tr><td>20</td><td>−175416</td></tr><tr><td>21</td><td>−389695</td></tr><tr><td>22</td><td>−865609</td></tr><tr><td>23</td><td>−1922362</td></tr><tr><td>24</td><td>−4268854</td></tr><tr><td>25</td><td>−9479595</td></tr><tr><td>26</td><td>−21051458</td></tr></tbody></table>
<h2 id="explanation">Explanation</h2>
There are three Algol features used in this program that can be difficult to implement properly in a compiler:

<ol><li><a href="/facts/Nested_function/Rw2xzMLP">Nested function</a> definitions: Since B is being defined in the local context of A, the body of B has access to symbols that are local to A — most notably k, which it modifies, but also x1, x2, x3, x4, and x5. This is straightforward in the Algol descendant <a href="/facts/Pascal_(programming_language)/b3yvp8bF">Pascal</a>, but not possible in the other major Algol descendant <a href="/facts/C_(programming_language)/Ky2No763">C</a> (without manually simulating the mechanism by using C's address-of operator, passing around pointers to local variables between the functions).</li>
<li><a href="/facts/Function_reference/dtMzp81k">Function references</a>: The B in the recursive call A(k, B, x1, x2, x3, x4) is not a call to B, but a reference to B, which will be called only when k is greater than zero. This is straightforward in standard Pascal (<a href="/facts/ISO_7185/b3yvp8bF">ISO 7185</a>), and also in C. Some variants of Pascal (e.g. older versions of <a href="/facts/Turbo_Pascal/2aWFEk9z">Turbo Pascal</a>) do not support procedure references, but when the set of functions that may be referenced is known beforehand (in this program it is only B), this can be worked around.</li>
<li>Constant/function dualism: The x1 through x5 parameters of A may be numeric constants or references to the function B — the x4 + x5 expression must be prepared to handle both cases as if the formal parameters x4 and x5 had been replaced by the corresponding actual parameter (<a href="/facts/Call_by_name/Pc9kLWgs">call by name</a>).<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> This is probably more of a problem in <a href="/facts/Statically_typed/Tz0bAMS9">statically typed</a> languages than in dynamically typed languages, but the standard workaround is to reinterpret the constants 1, 0, and −1 in the main call to A as functions without arguments that return these values.</li></ol>
These things are, however, not what the test is about; they are merely prerequisites for the test to at all be meaningful. What the test is about is whether the different references to B resolve to the correct instance of B — one that has access to the same A-local symbols as the B that created the reference. A "boy" compiler might, for example, instead compile the program so that B always accesses the topmost A call frame.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Funarg_problem/jafWEWqY">Funarg problem</a></li>
<li><a href="/facts/Jensen%2527s_device/GAfGwXBa">Jensen's device</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://rosettacode.org/wiki/Man_or_boy_test">Man or boy test</a> examples in many programming languages</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Ardö, Anders; Philipson, Lars (March 1984). "A simple Ada compiler invalidation test". ACM SIGAda Ada Letters. III (5): 69–74. doi:10.1145/998382.998385. ISSN 1094-3641. <a href="https://doi.org/10.1145%2F998382.998385" target="_blank">https://doi.org/10.1145%2F998382.998385</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Donald Knuth (July 1964). "Man or boy?". ALGOL Bulletin. 17: 7.
"AB17.2.4 Donald Knuth: Man or boy?, page 7". archive.computerhistory.org.
See also: "Algol Bulletin". Computing at Chilton: 1961–2000. Retrieved Dec 25, 2009. <a href="https://dl.acm.org/doi/10.5555/1060969.1060972" target="_blank">https://dl.acm.org/doi/10.5555/1060969.1060972</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Wichmann, B. A. (1972-02-01). "Five ALGOL Compilers". The Computer Journal. 15 (1): 8. doi:10.1093/comjnl/15.1.8. ISSN 0010-4620. <a href="https://academic.oup.com/comjnl/article-lookup/doi/10.1093/comjnl/15.1.8" target="_blank">https://academic.oup.com/comjnl/article-lookup/doi/10.1093/comjnl/15.1.8</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
</ol>

Man or boy test open-in-new

Man or boy test