Algorithme TPK - TPK algorithm

L' algorithme TPK est un programme simple introduit par Donald Knuth et Luis Trabb Pardo pour illustrer l'évolution des langages de programmation informatique . Dans leur ouvrage de 1977 "The Early Development of Programming Languages", Trabb Pardo et Knuth ont introduit un petit programme qui impliquait des tableaux , des indexations, des fonctions mathématiques , des sous - routines , des E/S , des conditions et des itérations . Ils ont ensuite écrit des implémentations de l'algorithme dans plusieurs premiers langages de programmation pour montrer comment ces concepts étaient exprimés.

Pour expliquer le nom « TPK », les auteurs se sont référés à la loi de Grimm (qui concerne les consonnes « t », « p » et « k »), les sons du mot « typique » et leurs propres initiales (Trabb Pardo et Knuth). Dans un discours basé sur le journal, Knuth a déclaré :

Vous ne pouvez apprécier la profondeur du sujet qu'en voyant à quel point les bonnes personnes ont lutté avec lui et comment les idées ont émergé une par une. Afin d'étudier cela—Je pense que Luis était le principal instigateur de cette idée—nous prenons un programme—un algorithme—et nous l'écrivons dans chaque langue. Et de cette façon, à partir d'un exemple, nous pouvons rapidement découvrir la saveur de cette langue particulière. Nous appelons cela le programme TPK, et le fait qu'il porte les initiales de Trabb Pardo et Knuth n'est qu'une drôle de coïncidence.

L'algorithme

Knuth le décrit ainsi :

Nous avons introduit une procédure simple appelée « algorithme TPK » et avons donné la saveur de chaque langue en exprimant TPK dans chaque style particulier. […] L'algorithme TPK saisit onze nombres ; puis il sort une séquence de onze paires où $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}.$

Cette tâche simple n'est évidemment pas vraiment un défi, dans n'importe quel langage informatique décent.

En pseudo-code :

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

L'algorithme lit onze nombres à partir d'un périphérique d'entrée, les stocke dans un tableau, puis les traite dans l'ordre inverse, en appliquant une fonction définie par l'utilisateur à chaque valeur et en signalant soit la valeur de la fonction, soit un message indiquant que la valeur a dépassé un certain seuil.

Implémentations

Implémentations dans l'article original

Dans l'article original, qui couvrait « à peu près la première décennie » du développement de langages de programmation de haut niveau (de 1945 à 1957), ils donnaient l'exemple d'implémentation suivant « dans un dialecte d' ALGOL 60 », notant que ALGOL 60 était un développement plus tardif que les langages réellement discutés dans l'article :

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.

Comme bon nombre des premiers langages de haut niveau ne pouvaient pas gérer exactement l'algorithme TPK, ils autorisent les modifications suivantes :

Si le langage ne prend en charge que les variables entières, supposez que toutes les entrées et sorties sont des valeurs entières, ce qui sqrt(x)signifie que le plus grand entier ne dépasse pas . ${\sqrt {x}}$

Si la langue ne prend pas en charge la sortie alphabétique, alors au lieu de la chaîne 'TOO LARGE', affichez le nombre 999.

Si le langage n'autorise aucune entrée et sortie, supposez que les 11 valeurs d'entrée ont été fournies par un processus externe d'une manière ou d'une autre, et la tâche consiste à calculer les 22 valeurs de sortie (avec 999 remplaçant les valeurs trop grandes de ). $a_{0},a_{1},\ldots ,a_{10}$ ${\style d'affichage 10,f(10),9,f(9),\ldots ,0,f(0)}$ ${\style d'affichage f(i)}$

Si le langage ne permet pas aux programmeurs de définir leurs propres fonctions, remplacez-le f(a[i])par une expression équivalente à . ${\sqrt {|a_{i}|}}+5x^{3}$

Avec ces modifications si nécessaire, les auteurs mettent en œuvre cet algorithme dans Konrad Zuse « s Plankalkül dans, Goldstine et von Neumann » s diagrammes de flux , en Haskell Curry notation proposée par, en code court de John Mauchly et d' autres, dans le programme intermédiaire Langue d' Arthur Burks , dans la notation de Heinz Rutishauser , dans le langage et le compilateur de Corrado Böhm en 1951-1952, dans l' Autocode d' Alick Glennie , dans le système A-2 de Grace Hopper , dans le système de Laning et Zierler , dans les premiers proposé Fortran (1954) de John Backus , dans l' Autocode for Mark 1 de Tony Brooker , dans ПП-2 de Andrey Ershov , dans BACAIC de Mandalay Grems et RE Porter, dans Kompiler 2 de A. Kenton Elsworth et autres, dans ADES de EK Blum, le traducteur interne d' Alan Perlis , en Fortran de John Backus, en ARITH-MATIC et MATH-MATIC du laboratoire de Grace Hopper , dans le système de Bauer et Samelson , et (en addenda en 2003 et 2009) PACT I et TRANSCODE. Ils décrivent ensuite quel type d'arithmétique était disponible et fournissent une évaluation subjective de ces langages sur les paramètres de "mise en œuvre", "lisibilité", "structures de contrôle", "structures de données", "indépendance de la machine" et "impact", en plus de mentionner ce que chacun a été le premier à faire.

Implémentations dans des langages plus récents

C mise en œuvre

Cela montre une implémentation C équivalente à l'ALGOL 60 ci-dessus.

#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 mise en œuvre

Cela montre une implémentation 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)

rouille mise en œuvre

Cela montre une implémentation de Rust.

use std::io::{self, prelude::*};

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

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

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

Languages

In other projects