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

В тест на мужчину или мальчика был предложен компьютерным ученым Дональд Кнут как средство оценки реализации АЛГОЛ 60 язык программирования. Целью теста было выявить компиляторы что правильно реализовано "рекурсия и нелокальные ссылки "от тех, кто этого не сделал.

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

— Дональд Кнут[1]

Пример Кнута

В АЛГОЛ 60:

начинать  настоящий процедура А(k, x1, x2, x3, x4, x5);  ценить k; целое число k;  настоящий x1, x2, x3, x4, x5;  начинать    настоящий процедура B;    начинать k := k - 1;          B := А := А(k, B, x1, x2, x3, x4)    конец;    если k ≤ 0 тогда А := x4 + x5 еще B  конец  нереальный(1,А(10, 1, -1, -1, 1, 0))конец

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

k
01
10
2−2
30
41
50
61
7−1
8−10
9−30
10−67
11−138
12−291
13−642
14−1,446
15−3,250
16−7,244
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 определяется в местном контексте А, тело B имеет доступ к символам, которые являются локальными для А - в первую очередь k который он изменяет, но также x1, x2, x3, x4, и x5. Это просто в потомке Алгола Паскаль, но невозможно в другом крупном потомке Алгола C (без ручного моделирования механизма с помощью оператора адресации C, передавая указатели на локальные переменные между функциями).
  2. Ссылки на функции: The B в рекурсивном вызове А (к, В, х1, х2, х3, х4) это не призыв к B, но ссылка на B, который будет вызываться только когда k больше нуля. Это просто в стандартном Паскале (ISO 7185 ), а также в C. Некоторые варианты Паскаля (например, более старые версии Турбо Паскаль ) не поддерживают ссылки на процедуры, но если набор функций, на которые можно ссылаться, известен заранее (в этой программе это только B), это можно обойти.
  3. Дуализм констант / функций: The x1 через x5 параметры А могут быть числовыми константами или ссылками на функцию B - в х4 + х5 выражение должно быть подготовлено для обработки обоих случаев, как если бы формальные параметры x4 и x5 был заменен соответствующим фактическим параметром (позвонить по имени ). Вероятно, это больше проблема в статически типизированный языков, чем в языках с динамической типизацией, но стандартный обходной путь - переинтерпретировать константы 1, 0 и −1 в основном вызове А как функции без аргументов, возвращающие эти значения.

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

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

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

  1. ^ Дональд Кнут (Июль 1964 г.). "Мужчина или мальчик?". Получено 25 декабря, 2009.
  2. ^ Посмотрите производительность и память на странице Rosetta Code Man или Boy.

внешняя ссылка