Алгоритм ТПК - TPK algorithm

В Алгоритм ТПК это программа представлен Дональд Кнут и Луис Трабб Пардо чтобы проиллюстрировать эволюцию компьютера языки программирования. В своей работе 1977 года «Раннее развитие языков программирования» Трабб Пардо и Кнут представили небольшую программу, в которой участвовали: массивы, индексация, математическая функции, подпрограммы, Ввод / вывод, условные и итерация. Затем они написали реализации алгоритма на нескольких ранних языках программирования, чтобы показать, как были выражены такие концепции.

Чтобы объяснить название «ТПК», авторы сослались на Закон Гримма (что касается согласных «т», «р» и «к»), звуков в слове «типичный» и их собственных инициалов (Трабб Пардо и Кнут).[1] В докладе, основанном на статье, Кнут сказал:[2]

Вы можете оценить, насколько глубок этот предмет, только увидев, как хорошие люди боролись с ним и как идеи возникали по очереди. Чтобы изучить это - я думаю, Луис был главным вдохновителем этой идеи - мы берем одну программу - один алгоритм - и пишем ее на всех языках. Таким образом, на одном примере мы можем быстро понять вкус этого конкретного языка. Мы называем это программой ТПК, и то, что в ней написаны инициалы Трабб Пардо и Кнут, - просто забавное совпадение.

В статье авторы реализуют этот алгоритм в Конрад Зузе с Plankalkül, в Голдстайн и фон Нейман с блок-схемы, в Хаскелл Карри предлагаемые обозначения в Короткий код из Джон Мочли и другие, на промежуточном языке программы Артур Беркс, в обозначениях Хайнц Рутисхаузер, на языке и компиляторе Коррадо Бём в 1951–52 гг., в Автокодирование из Алик Гленни, в А-2 система Грейс Хоппер, в Система Ланинга и Цирлера, в самом раннем предложенном Фортран (1954) из Джон Бэкус, в Автокодирование за Марка 1 к Тони Брукер, в ПП-2 г. Андрей Ершов, в BACAIC Мандалая Гремса и Р. Э. Портера, в Компиляторе 2 А. Кентона Элсворта и других, в ADES Э. К. Блюма, внутреннего переводчика Алан Перлис, в Фортран Джона Бэкуса в АРИФ-МАТИЧЕСКИЙ и МАТЕМАТИЧЕСКИЙ из Грейс Хоппер лаборатории, в системе Бауэр и Самельсон и (в дополнениях в 2003 и 2009 гг.) ПАКТ I и ТРАНСКОД. Затем они описывают, какой вид арифметики был доступен, и предоставляют субъективную оценку этих языков по параметрам «реализация», «удобочитаемость», «управляющие структуры», «структуры данных», «машинная независимость» и «влияние», помимо упоминания что каждый сделал первым.

Алгоритм

просить для 11 чисел, читаемых в последовательность Sобеспечить регресс последовательность Sдля каждого элемент в последовательность S    вызов функция для выполнения операции если результат переливается тревога Пользователь еще        Распечатать результат

Алгоритм считывает одиннадцать чисел с устройства ввода, сохраняет их в массиве, а затем обрабатывает их в обратном порядке, применяя определяемую пользователем функцию к каждому значению и сообщая либо значение функции, либо сообщение о том, что значение превысил некоторый порог.

АЛГОЛ 60 выполнение

 1 начинать целое число я; настоящий у; настоящий множество а[0:10]; 2    настоящий процедура ж(т); настоящий т; ценить т; 3       ж := sqrt(пресс(т)) + 5 * т ^ 3; 4    за я := 0 шаг 1 до того как 10 делать читать(а[я]); 5    за я := 10 шаг -1 до того как 0 делать 6    начинать у := ж(а[я]); 7       если у > 400 тогда записывать(я, "ТОЖЕ БОЛЬШОЙ") 8                  еще записывать(я, у); 9    конец10 конец.

Проблема с обычно указанной функцией заключается в том, что термин 5 * т ^ 3 дает переполнение почти на всех языках для очень больших отрицательных значений.

C выполнение

Это показывает реализацию C, эквивалентную вышеупомянутому АЛГОЛУ 60.

 1 #включают <math.h> 2 #включают <stdio.h> 3  4 двойной ж(двойной т) 5 { 6     возвращаться sqrt(фабрики(т)) + 5 * пау(т, 3); 7 } 8  9 int главный(пустота)10 {11     двойной а[11], у;12     за (int я = 0; я < 11; я++)13         сканф("% lf", &а[я]);14 15     за (int я = 10; я >= 0; я--) {16         у = ж(а[я]);17         если (у > 400)18             printf("% d СЛИШКОМ БОЛЬШОЙ п", я);19         еще20             printf("% d% .16g п", я, у);21     }22 }

Python выполнение

Это показывает реализацию Python.

 1 из математика импорт sqrt 2  3 def ж(т): 4     возвращаться sqrt(пресс(т)) + 5 * т ** 3 5  6 а = [плавать(Вход()) за _ в классифицировать(11)] 7 за я, т в перевернутый(список(перечислять(а))): 8     у = ж(т) 9     если у > 400:10         Распечатать(я, "СЛИШКОМ БОЛЬШОЙ")11     еще:12         Распечатать(я, у)

Ржавчина выполнение

Это показывает реализацию Rust.

 1 использоватьстандартное::io::{стандартный ввод,BufRead}; 2  3 fn ж(т: f64)-> f64 { 4 т.пресс().sqrt()+5.0*т.Powi(3) 5 } 6  7 fn главный(){ 8 позволятьмута=[0f64;11]; 9 за(т,Вход)ва.iter_mut().застегивать(стандартный ввод().замок().линии()){10 *т=Вход.развернуть().разбирать().развернуть();11 }12 13 а.iter().перечислять().rev().для каждого(|(я,&т)|матчж(т){14 уеслиу>400.0=>println!("{} СЛИШКОМ БОЛЬШОЙ",я),15 у=>println!("{} {}",я,у),16 });17 }

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

  1. ^ Луис Трабб Пардо и Дональд Э. Кнут, «Раннее развитие языков программирования».
    • Впервые опубликовано в августе 1976 г. в машинописный черновик, как Stanford CS Report STAN-CS-76-562
    • Опубликовано в Энциклопедия компьютерных наук и технологий, Джек Белзер, Альберт Г. Хольцман и Аллен Кент (ред.), Vol. 6. С. 419-493. Деккер, Нью-Йорк, 1977.
    • Перепечатано (Дои:10.1016 / B978-0-12-491650-0.50019-8 ) в История вычислений в двадцатом веке, Н. Метрополис, Дж. Хоулетт, и Г.-К. Рота (ред.), Нью-Йорк, Academic Press, 1980. ISBN  0-12-491650-3
    • Печатается с поправками как Глава 1 Избранные статьи по компьютерным языкам, Дональд Кнут, Стэнфорд, Калифорния, CSLI, 2003. ISBN  1-57586-382-0)
  2. ^ «Дюжина предшественников Фортрана», лекция Дональда Кнута, 2003-12-03 в Музей истории компьютеров: Абстрактный, видео

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