Алгоритм ТПК

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

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

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

Алгоритм

Кнут описывает это следующим образом:

Мы представили простую процедуру, называемую «алгоритмом TPK», и придали особенности каждого языка, выражая TPK в каждом конкретном стиле. […] Алгоритм TPK вводит одиннадцать чисел. $a_{0},a_{1},\ldots ,a_{10}$; затем он выводит последовательность из одиннадцати пар $(10,b_{10}),(9,b_{9}),\ldots ,(0,b_{0}),$ где

$b_{i}={\begin{cases}f(a_{i}),&{\text{if }}f(a_{i})\leq 400;\\999,&{\text{if }}f(a_{i})>400;\end{cases}}\quad f(x)={\sqrt {|x|}}+5x^{3}.$

Эта простая задача, очевидно, не является большой проблемой на любом приличном компьютерном языке.

В псевдокоде:

ask for 11 numbers to be read into a sequence S
reverse sequence S
for each item in sequence S
    call a function to do an operation
    if result overflows
        alert user
    else
        print result

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

Реализации

Реализации в оригинальной статье

В оригинальной статье, охватывающей «примерно первое десятилетие» развития языков программирования высокого уровня (с 1945 по 1957 год), они привели следующий пример реализации «на диалекте АЛГОЛа 60 », отметив, что АЛГОЛ 60 был более позднее развитие, чем языки, обсуждаемые в статье:

TPK: begin integer i; real y; real array a[0:10];
   real procedure f(t); real t; value t;
      f := sqrt(abs(t)) + 5 × t ↑ 3;
   for i := 0 step 1 until 10 do read(a[i]);
   for i := 10 step -1 until 0 do
   begin y := f(a[i]);
      if y > 400 then write(i, 'TOO LARGE')
                 else write(i, y);
   end
end TPK.

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

• Если язык поддерживает только целочисленные переменные, предположим, что все входные и выходные данные имеют целочисленные значения и что sqrt(x) означает наибольшее целое число , не превышающее ${\sqrt {x}}$.

• Если язык не поддерживает буквенный вывод, то вместо строки 'TOO LARGE', выведите число 999.

• Если язык не допускает ввода и вывода, то предположим, что 11 входных значений $a_{0},a_{1},\ldots ,a_{10}$ были каким-то образом предоставлены внешним процессом, и задача состоит в том, чтобы вычислить 22 выходных значения. $10,f(10),9,f(9),\ldots ,0,f(0)$ (999 заменяет слишком большие значения $f(i)$).

• Если язык не позволяет программистам определять свои собственные функции, то замените f(a[i]) с выражением, эквивалентным ${\sqrt {|a_{i}|}}+5x^{3}$.

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

Реализации на более поздних языках

C- реализация

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

#include <math.h>
#include <stdio.h>

double f(double t)
{
    return sqrt(fabs(t)) + 5 * pow(t, 3);
}

int main(void)
{
    double a[11] = {0}, y;
    for (int i = 0; i < 11; i++)
        scanf("%lf", &a[i]);

    for (int i = 10; i >= 0; i--) {
        y = f(a[i]);
        if (y > 400)
            printf("%d TOO LARGE\n", i);
        else
            printf("%d %.16g\n", i, y);
    }
}

Python Реализация

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

from math import sqrt

def f(t):
    return sqrt(abs(t)) + 5 * t ** 3

a = [float(input()) for _ in range(11)]
for i, t in reversed(list(enumerate(a))):
    y = f(t)
    print(i, "TOO LARGE" if y > 400 else y)

ржавчины Реализация

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

use std::{io, iter::zip};

fn f(t: f64) -> f64 {
    t.abs().sqrt() + 5.0 * t.powi(3)
}

fn main() {
    let mut a = [0f64; 11];
    for (t, input) in zip(&mut a, io::stdin().lines()) {
        *t = input.unwrap().parse().unwrap();
    }

    a.iter().enumerate().rev().for_each(|(i, &t)| match f(t) {
        y if y > 400.0 => println!("{i} TOO LARGE"),
        y => println!("{i} {y}"),
    });
}

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

• Реализации на многих языках в Rosetta Code
• Реализации на нескольких языках