TPKアルゴリズムのソースを表示


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

“TPK” の名前について，作者は[[グリムの法則]]（[[ゲルマン語]]の[[子音]] [[無声歯茎破裂音|/t/]], [[無声両唇破裂音|/p/]]と[[無声軟口蓋破裂音|/k/]]に関する法則），“typical” という語の発音（[[国際音声記号|IPA]]: [ˈtɪ.pɪ.k(ə)l]），および名前のイニシャル（[[T]]<nowiki/>rabb [[P]]<nowiki/>ardo と [[K]]<nowiki/>nuth）に言及した。クヌースはその論文に基づいたトークで，以下のように述べた：

{{Quote|このテーマがいかに深いかは，人々がどれほどもがき，アイデア一つ一つがどのようにして生まれたのか考えければ理解できない。これを研究するために，—ルイスがこのアイデアの中心的な発案者だと思うが—我々はプログラム—あるいはアルゴリズム—を一つとって，すべての言語でそれをコードに書く。そうして，一つの例から，直ちにその特定の言語の特徴を分析できる。これをTPKプログラムと呼ぶが，これがTrabb PardoとKnuthのイニシャルになっているのはただの面白い偶然に過ぎない。}}

== アルゴリズム ==
クヌースは以下のように説明する：
{{Quote|「TPKアルゴリズム」と呼ばれる簡単な手続きを導入し，各言語に対してそれぞれ独自のスタイルでプログラムを書くことで特徴を見出した。[…] TPKアルゴリズムは，11個の数<math>a_0, a_1, \ldots, a_{10}</math>を入力し，以下の定義によって11個の数の組<math>(10, b_{10}), (9, b_9), \ldots, (0, b_0),</math>を出力する。
定義：
<math>b_i = \begin{cases}
    f(a_i), & \text{if }f(a_i) \le 400; \\
    999, & \text{if }f(a_i) > 400; \end{cases}</math>

ここに<math>f(x) = \sqrt{|x|} + 5x^3</math>
この簡単な手続きは明らかにどのまとものコンピュータ言語でも大したことはない。}}
擬似言語：
 '''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の方言」での実行の例を挙げた（以下）。 <syntaxhighlight lang="Pascal" line="">
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.
</syntaxhighlight>初期の[[高水準言語]]の多くはTPKアルゴリズムを正確に処理できなかったため，以下の修正を認めた：

* もしその言語が整数の変数にしか対応していないなら，すべての入力と出力が整数値関数済であり，<code>sqrt(x)</code> が<math>\sqrt{x}</math>を超えない最大の「整数」を意味すると仮定する。

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

* もしその言語が入力と出力を'''一切'''認めないなら，11の入力の値 <math>a_0, a_1, \ldots, a_{10}</math> は何らかの方法で外部プロセスによって与えられたものと仮定し，タスクを[[22]]の出力の値 <math>10, f(10), 9, f(9), \ldots, 0, f(0)</math> (ただし<math>f(i)</math>の値が大きすぎる場合は999に置換) を計算することと考える。

* もしその言語が関数定義を認めないなら，<code>f(a[i])</code>を定義式<math>\sqrt{|a_i|} + 5 a^3_i</math>で置換する。

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

# [[コンラート・ツーゼ]]の[[プランカルキュール]]
# [[ハーマン・ゴールドスタイン]]と[[ジョン・フォン・ノイマン]]の[[フローチャート]]
# [[ハスケル・カリー]]が提唱した記法
# [[ジョン・モークリー]]らの[[Short Code (プログラミング言語)|Short Code]]
# [[アーサー・バークス]]のIntermediate Program Language
# [[ハインツ・ルティスハウザー]]の記法
# [[コラド・ベーム]]の言語とコンパイラ（1951～52）
# アリク・グレニーの[[Autocode]]
# [[グレース・ホッパー]]の[[A-0 System|A-2]]システム
# Laning and Zierler system
# [[ジョン・バッカス]]の最初に提唱された[[フォートラン]]（1954）
# トニー・ブルッカーによる[[Autocode]] for [[Manchester Mark I|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言語|C]]言語 ====
<syntaxhighlight lang="C" line="">
#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;

}
</syntaxhighlight>

==== [[Python]] ====
<syntaxhighlight lang="python" line="">
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)
</syntaxhighlight>

==== [[Rust (プログラミング言語)|Rust]] ====
<syntaxhighlight lang="Rust" line="">
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}"),
    });
}
</syntaxhighlight>

== 外部リンク ==

* [https://rosettacode.org/wiki/Trabb_Pardo%E2%80%93Knuth_algorithm Implementations in many languages] at ''[[:en:Rosetta_Code|Rosetta Code]]''
* [http://cs.fit.edu/~ryan/compare Implementations in several languages]


[[Category:プログラミング・フォークロア]]
[[Category:ドナルド・クヌース]]