Тест на мужчину или мальчика - Man or boy test

Тест « мужчина или мальчик» был предложен компьютерным ученым Дональдом Кнутом как средство оценки реализаций языка программирования 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(A(10, 1, -1, -1, 1, 0))
end;

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

k
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

Объяснение

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

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

Однако тест не об этом; они всего лишь предварительные условия для того, чтобы тест был хоть сколько-нибудь значимым. Что тест о ли различных ссылках на B решимость к правильному экземпляру B - тот , который имеет доступ к тем же А -локальным символам , как B , создавшей ссылке. Компилятор "мальчик" мог бы, например, вместо этого скомпилировать программу так, чтобы B всегда обращался к самому верхнему кадру вызова A.

Смотрите также

Рекомендации

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