TPK 알고리즘

TPK 알고리즘은 도널드 크누스와 루이스 트래브 파르도가 컴퓨터 프로그래밍 언어의 진화를 설명하기 위해 도입한 간단한 프로그램이다. 트라브 파르도와 크누스는 1977년 저서 '프로그래밍 언어의 초기 개발'에서 배열, 색인화, 수학 함수, 서브루틴, I/O, 조건화 및 반복을 포함하는 작은 프로그램을 소개했다. 그리고 나서 그들은 그러한 개념들이 어떻게 표현되는지를 보여주기 위해 알고리즘의 구현을 몇 개의 초기 프로그래밍 언어로 작성했다.

'TPK'라는 이름을 설명하기 위해 저자들은 그림의 법칙('t', 'p', 'k'의 자음과 관련된 것), '일반'이라는 단어의 소리, 그리고 그들 자신의 이니셜(Trabb Pardo와 Knuth)을 언급했다.^[1] 이 신문에 근거한 강연에서 크누스는 다음과 같이 말했다.^[2]

사람들이 얼마나 잘 헤쳐 나갔는지, 그리고 어떻게 아이디어가 한 번에 하나씩 생겨났는지를 보아야만 주제의 깊이를 알 수 있다. 이것을 연구하기 위해서-Luis 나는 우리가 하나의 프로그램, 하나의 알고리즘을 가지고 모든 언어로 그 아이디어를 쓰는 이 아이디어의 주창자라고 생각한다. 그리고 한 예에서 우리는 그 특정한 언어의 맛을 재빨리 알아낼 수 있다. 우리는 이것을 TPK 프로그램이라고 부르는데, 뭐, 트라브 파르도와 크누스의 이니셜을 가지고 있다는 것은 그저 우스운 우연일 뿐이다.

알고리즘

크누스는 다음과 같이 설명한다.^[3]

「TPK 알고리즘」이라고 하는 간단한 절차를 도입해, 각각의 특정한 스타일로 TPK를 표현해 각 언어의 풍미를 부여했다. […] The TPK algorithm inputs eleven numbers ${\displaystyle a_{0},a_{1},\ldots ,a_{10}}$; then it outputs a sequence of eleven pairs ${\displaystyle (10,b_{10}),(9,b_{9}),\ldots ,(0,b_{0}),}$ where

${\displaystyle b_{i}={\case}f(a_{i}),&{\text{f(a_{i})\leq 400;\\999,&\text{{{f(a_{i})}}}}}}}}}}{{prease}}={\sqrt{{}+5x^{}.}$

이 간단한 작업은 어떤 점잖은 컴퓨터 언어에서도 분명히 큰 어려움은 아니다.

유사 코드:

시퀀스 S의 각 항목에 대해 11개의 숫자를 읽을 것을 요청한다. 시퀀스 S의 각 항목에 대해 역순으로 읽도록 요청한다. 결과가 오버플로되면 작업을 수행하기 위해 함수를 호출한다. 그렇지 않으면 인쇄 결과를 사용자에게 알린다. 

알고리즘은 입력 장치에서 11개의 숫자를 읽고 배열로 저장한 다음 역순으로 처리하여 각 값에 사용자 정의 함수를 적용하고 값이 일부 임계값을 초과했다는 효과에 대해 함수 값이나 메시지를 보고한다.

구현

원본 문서의 구현

그들은 상위 프로그래밍 언어의 발달(1945년부터 1957년까지)의 「거의 첫 10년」을 다룬 원 논문에서, ALGOL 60이 실제로 논한 언어보다 후기의 발전이라는 점에 주목하면서, 「ALLGOL 60의 방언으로」의 구현 예를 제시했다.^[1]

TPK: 시작되다 정수의 i; 진짜 y; 진짜 배열하다 a[0:10];    진짜 절차 f(t); 진짜 t; 가치를 매기다 t;       f := sqrt(복근(t)) + 5 × t ↑ 3;    을 위해 i := 0 스텝을 밟다 1 까지 10 하다 읽다(a[i]);    을 위해 i := 10 스텝을 밟다 -1 까지 0 하다    시작되다 y := f(a[i]);       만일 y > 400 그때 글씨를 쓰다(i, '너무 크다')                  다른 글씨를 쓰다(i, y);    종지부를 찍다 종지부를 찍다 TPK. 

초기 상위 언어의 다수가 TPK 알고리즘을 정확하게 다룰 수 없었기 때문에 다음과 같은 수정을 허용한다.^[1]

• 언어가 정수 변수만 지원하는 경우 모든 입력 및 출력이 정수 값이라고 가정하고 sqrt(x) $x{\displaystyle \sqrt{}}$ ${\$를 초과하지 않는 가장 큰 정수를 의미한다$.$

• 언어가 영문자 출력을 지원하지 않는 경우 문자열 대신 'TOO LARGE', 숫자 999를 출력한다.

• If the language does not allow any input and output, then assume that the 11 input values ${\displaystyle a_{0},a_{1},\ldots ,a_{10}}$ have been supplied by an external process somehow, and the task is to compute the 22 output values ${\displaystyle 10,f(10),9$$,f(9),\ldots ,0,f(0)}($999가 $f{\displaystyle }$(${\displaystyle i}$ ${\displaystyle )}$ ${\displaystyle f(i)}$의 너무 큰 값을 대체함).$$

• 언어가 프로그래머가 자신의 기능을 정의할 수 없는 경우, 그 다음 f(a[i]) ${\displaystyle \sqrt{i_{}{}_{}}}$+ 5 ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$ ${\$에 해당하는 식을 사용하여$}}$.

With these modifications when necessary, the authors implement this algorithm in Konrad Zuse's Plankalkül, in Goldstine and von Neumann's flow diagrams, in Haskell Curry's proposed notation, in Short Code of John Mauchly and others, in the Intermediate Program Language of Arthur Burks, in the notation of Heinz Rutishauser, in the language and compiler by Corrado Böhm in 1951–52, in Autocode of Alick Glennie, in the A-2 system of Grace Hopper, in the Laning and Zierler system, in the earliest proposed Fortran (1954) of John Backus, in the Autocode for Mark 1 by Tony Brooker, in ПП-2 of Andrey Ershov, in BACAIC of Mandalay Grems and R. E. Porter, in Kompiler 2 of A. Kenton Elsworth and others, in ADES of E. K. Blum, the Internal Translator of Alan Perlis, in Fortran of John Backus, in ARITH-MATIC and MATH-MATIC from Grace Hopper's lab, in the system of Bauer and Samelson, and (in addenda in 2003 and 2009) PACT I and TRANSCODE. 그런 다음 어떤 종류의 산수를 사용할 수 있었는지 설명하고, 각 언어의 첫 번째 작업을 언급하는 것 외에 "실행", "읽기 가능성", "제어 구조", "데이터 구조", "기계 독립성" 및 "충격" 매개변수에 대해 이러한 언어의 주관적 등급을 제공한다.^[1]

최신 언어로 구현

C 구현

이것은 위의 ALGOL 60과 동등한 C 구현을 보여준다.

#include <수학.h> #include <stdio.h>  곱절로 하다 f(곱절로 하다 t) {     돌아오다 sqrt(팹(t)) + 5 * 포우(t, 3); }  인트로 본래의(공허하게 하다) {     곱절로 하다 a[11] = {0}, y;     을 위해 (인트로 i = 0; i < 11; i++)         스캔하다("%lf", &a[i]);      을 위해 (인트로 i = 10; i >= 0; i--) {         y = f(a[i]);         만일 (y > 400)             활자화하다("%d 너무 큼\n", i);         다른             활자화하다("%d %.16g\n", i, y);     }         돌아오다 0;  } 

파이썬 구현

이것은 Python 구현을 보여준다.

로부터 수학 수입하다 sqrt  반항하다 f(t):     돌아오다 sqrt(복근(t)) + 5 * t ** 3  a = [둥둥 뜨다(입력하다()) 을 위해 _ 에 범위(11)] 을 위해 i, t 에 뒤바뀐(리스트를 작성하다(열거하다(a))):     y = f(t)     만일 y > 400:         인쇄하다(i, "너무 큼")     다른:         인쇄하다(i, y) 

녹 이행

이것은 러스트 구현을 보여준다.

std::io: 사용:{{self, 전주곡::*};    fnf(t: f64) -> f64{     t.복근().sqrt() + 5.0 * t.포와이(3) }   fn본래의() {     하게 하다 돌연변이를 일으키다 a = [0f64; 11];  (t, 입력)는 a.iter_infilename().zip(io::stdin().lock().lines()) {         *t = 입력하다.포장을 풀다().파스를 치다().포장을 풀다();     }      a.into_iter.().열거하다().회전시키다().각각용( (i, t)  짝을 맞추다 f(t) {         y 만일 y > 400.0 => 인쇄하다!("{i} 너무 큼"),         y => 인쇄하다!("{i} {y}"),     }); } 

참조

외부 링크

• Rosetta Code에서 여러 언어로 구현
• 여러 언어로 된 구현