Тест мужчина или мальчик

Тест «мужчина или мальчик» был предложен ученым-компьютерщиком Дональдом Кнутом как средство оценки реализаций языка программирования ALGOL 60 . Целью теста было отличить компиляторы , которые правильно реализовали « рекурсию и нелокальные ссылки », от тех, которые этого не сделали.

Существует довольно много трансляторов ALGOL60, которые были разработаны для правильной обработки рекурсии и нелокальных ссылок, и я подумал, что, возможно, небольшая тестовая программа может оказаться полезной. Поэтому я написал следующую простую программу, которая может отличить компиляторов-мужчин от компиляторов-мальчиков.

— Дональд Кнут

Пример Кнута

В АЛГОЛЕ 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

При этом создается дерево кадров вызова B , которые ссылаются друг на друга и на содержащиеся в нем кадры вызова A , каждый из которых имеет свою собственную копию k связанный с ним B. , которая меняется каждый раз, когда вызывается Попытка решить это на бумаге, вероятно, бесплодна, но для k = 10 правильный ответ — −67, несмотря на то, что в оригинальной статье Кнут предположил, что оно равно −121. Даже современным машинам быстро не хватает места в стеке для больших значений k , которые приведены в таблице ниже ( OEIS : A132343 ).

к	‍ $A(k,1,-1,-1,1,0)$‍
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

Объяснение

В этой программе используются три функции Алгола, которые может быть сложно правильно реализовать в компиляторе:

1. вложенных функций Определения : поскольку B определяется в локальном контексте A , тело B имеет доступ к символам, которые являются локальными для A — в первую очередь k , который он изменяет, а также x1 , x2 , x3 , x4 и x5. . Это просто в потомке Алгола Pascal , но невозможно в другом основном потомке Алгола C (без ручного моделирования механизма с использованием оператора адреса C, передавая указатели на локальные переменные между функциями).
2. Ссылки на функции : буква B в рекурсивном вызове. A(k, B, x1, x2, x3, x4) это не вызов B , а ссылка на B , которая будет вызываться только тогда, когда k больше нуля. Это просто в стандартном Паскале ( ISO 7185 ), а также в C. Некоторые варианты Паскаля (например, более старые версии Turbo Pascal ) не поддерживают ссылки на процедуры, но когда набор функций, на которые можно ссылаться, известен заранее (в этом программа это только B ), это можно обойти.
3. Дуализм констант/функций : от x1 до x5 параметры A могут быть числовыми константами или ссылками на функцию B – x4 + x5 Выражение должно быть подготовлено для обработки обоих случаев, как если бы формальные параметры x4 и x5 были заменены соответствующим фактическим параметром ( вызов по имени ). Вероятно, это большая проблема для статически типизированных языков, чем для динамически типизированных языков, но стандартным обходным решением является переинтерпретация констант 1, 0 и -1 в основном вызове A как функций без аргументов, возвращающих эти значения.

Однако суть теста не в этом; они являются лишь предпосылками для того, чтобы тест вообще имел смысл. проверки является Целью то, разрешаются ли различные ссылки на B в правильный экземпляр B — тот, который имеет доступ к тем же A -локальным символам, что и B , создавший ссылку. Например, «мальчик»-компилятор может вместо этого скомпилировать программу так, чтобы B всегда обращался к самому верхнему A. кадру вызова

См. также

• Проблема Фунарга
• Устройство Дженсена

Внешние ссылки

• Примеры тестов для мужчин и мальчиков на многих языках программирования