TPKアルゴリズム

TPKアルゴリズムはドナルド・クヌースとルイス・トラブ・パルドがコンピュータのプログラミング言語の進化を説明するために紹介した簡単なプログラムである。1976年８月の論文『プログラミング言語の初期開発』（原題 “The Early Development of Programming Languages” ）の中で，配列，インデクス，数学的関数，サブルーチン，入出力，条件分岐と繰り返しに関する小さなプログラムを紹介した。次に初期のプログラミング言語でのアルゴリズムの実装を記してその概念がどう表現されるか説明した。

“TPK” の名前について，作者はグリムの法則（ゲルマン語の子音 /t/, /p/と/k/に関する法則），“typical” という語の発音（IPA: [ˈtɪ.pɪ.k(ə)l]），および名前のイニシャル（Trabb Pardo と Knuth）に言及した。クヌースはその論文に基づいたトークで，以下のように述べた：

 アルゴリズム 
クヌースは以下のように説明する：

擬似言語：
 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
このアルゴリズムは入力から11の数を受け取って配列に格納し，逆順にしてから，ユーザー定義の関数を各数に適用して関数の返り値またはその値が閾値を超越した旨のメッセージを報告する。

 実装 

 論文で説明された実装 
初版の高水準プログラミング言語の開発の「だいたい最初の10年をカバーした」（1945年から1957年まで）論文では，ALGOL 60 が論文で実際に議論された言語より後の開発であることを注記した上で「ALGOL 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) がを超えない最大の「整数」を意味すると仮定する。

 もしその言語がアルファベットの出力に対応していないなら，“TOO LARGE”（過剰）の文字列の代わりに999を出力する。

 もしその言語が入力と出力を一切認めないなら，11の入力の値  は何らかの方法で外部プロセスによって与えられたものと仮定し，タスクを22の出力の値  (ただしの値が大きすぎる場合は999に置換) を計算することと考える。

 もしその言語が関数定義を認めないなら，f(a[i])を定義式で置換する。

必要ならこれらの修正を施し，作者らはこのアルゴリズムを以下で実装する：

 コンラート・ツーゼのプランカルキュール
 ハーマン・ゴールドスタインとジョン・フォン・ノイマンのフローチャート
 ハスケル・カリーが提唱した記法
 ジョン・モークリーらのShort Code
 アーサー・バークスのIntermediate Program Language
 ハインツ・ルティスハウザーの記法
 コラド・ベームの言語とコンパイラ（1951～52）
 アリク・グレニーのAutocode
 グレース・ホッパーのA-2システム
 Laning and Zierler system
 ジョン・バッカスの最初に提唱されたフォートラン（1954）
 トニー・ブルッカーによるAutocode for Mark 1
 アンドレイ・エルショフのПП-2
 Mandalay GremsとR. E. PorterによるBACAIC
 A. Kenton ElsworthらのKompiler 2
 E. K. BlumのADES
 アラン・パリスのthe Internal Translator
 ジョン・バッカスのフォートラン
 グレース・ホッパーの研究室のARITH-MATICとMATH-MATIC
 フリードリッヒ・L・バウアーとクラウス・サメルソンのシステム
 (2003・2009追記)PACT I
 TRANSCODE

そしてどのような演算が利用可能かの説明があり，これらの言語の「実装」，「可読性」，「制御構造」，「データ構造」，「機械独立性」と「インパクト」の観点からの主観評価，さらにそれぞれ最初にしたことが続く。

 より最近の言語での実装 

 C言語 
#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);
    }

    return 0;

}

 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)
    if y > 400:
        print(i, "TOO LARGE")
    else:
        print(i, 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}"),
    });
}

 外部リンク 

 Implementations in many languages at Rosetta Code
 Implementations in several languages

Category:プログラミング・フォークロア
Category:ドナルド・クヌース
Category:テストアイテム