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

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.

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