Algoritmo TPK - TPK algorithm

O algoritmo TPK é um programa simples apresentado por Donald Knuth e Luis Trabb Pardo para ilustrar a evolução das linguagens de programação de computador . Em seu trabalho de 1977 "O Desenvolvimento Inicial das Linguagens de Programação", Trabb Pardo e Knuth introduziram um pequeno programa que envolvia matrizes , indexação, funções matemáticas , sub-rotinas , E / S , condicionais e iteração . Eles então escreveram implementações do algoritmo em várias linguagens de programação antigas para mostrar como tais conceitos eram expressos.

Para explicar o nome "TPK", os autores se referiram à lei de Grimm (que diz respeito às consoantes 't', 'p' e 'k'), aos sons da palavra "típico" e às suas próprias iniciais (Trabb Pardo e Knuth). Em uma palestra baseada no jornal, Knuth disse:

Você só pode avaliar a profundidade do assunto vendo como boas pessoas lutaram contra ele e como as ideias surgiram uma de cada vez. Para estudar isso - acho que Luis foi o principal instigador dessa ideia - pegamos um programa - um algoritmo - e o escrevemos em todas as linguagens. E dessa forma, a partir de um exemplo, podemos rapidamente descobrir o sabor dessa linguagem em particular. Chamamos isso de programa TPK, e bem, o fato de ter as iniciais de Trabb Pardo e Knuth é apenas uma coincidência engraçada.

O algoritmo

Knuth o descreve da seguinte maneira:

Introduzimos um procedimento simples chamado “algoritmo TPK” e demos o sabor de cada linguagem, expressando o TPK em cada estilo particular. […] O algoritmo TPK insere onze números ; em seguida, ele produz uma sequência de onze pares onde ${\ displaystyle a_ {0}, a_ {1}, \ ldots, a_ {10}}$ ${\ displaystyle (10, b_ {10}), (9, b_ {9}), \ ldots, (0, b_ {0}),}$

${\ displaystyle 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}.}$

Esta tarefa simples obviamente não é um grande desafio, em qualquer linguagem de computador decente.

Em pseudocódigo:

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

O algoritmo lê onze números de um dispositivo de entrada, armazena-os em uma matriz e, em seguida, os processa na ordem inversa, aplicando uma função definida pelo usuário a cada valor e relatando o valor da função ou uma mensagem informando que o valor excedeu algum limite.

Implementações

Implementações no artigo original

No artigo original, que cobriu "aproximadamente a primeira década" do desenvolvimento de linguagens de programação de alto nível (de 1945 a 1957), eles deram o seguinte exemplo de implementação "em um dialeto do ALGOL 60 ", observando que o ALGOL 60 foi um desenvolvimento posterior às linguagens realmente discutidas no artigo:

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.

Como muitas das primeiras linguagens de alto nível não conseguiam lidar com o algoritmo TPK exatamente, elas permitem as seguintes modificações:

Se a linguagem suportar apenas variáveis inteiras, então suponha que todas as entradas e saídas tenham valores inteiros, e isso sqrt(x)significa que o maior inteiro não excede . ${\ displaystyle {\ sqrt {x}}}$

Se o idioma não suportar saída alfabética, em vez da string 'TOO LARGE', imprima o número 999.

Se a linguagem não permite nenhuma entrada e saída, então suponha que os 11 valores de entrada foram fornecidos por um processo externo de alguma forma, e a tarefa é calcular os 22 valores de saída (com 999 substituindo valores muito grandes de ). ${\ displaystyle a_ {0}, a_ {1}, \ ldots, a_ {10}}$ ${\ displaystyle 10, f (10), 9, f (9), \ ldots, 0, f (0)}$ ${\ displaystyle f (i)}$

Se a linguagem não permitir que os programadores definam suas próprias funções, substitua f(a[i])por uma expressão equivalente a . ${\ displaystyle {\ sqrt {| a_ {i} |}} + 5x ^ {3}}$

Com estas modificações quando necessário, os autores implementar este algoritmo em Konrad Zuse 's Plankalkül , em Goldstine e von Neumann ' s diagramas de fluxo , em Haskell Curry notação proposta 's, no código curto de John Mauchly e outros, no Intermediate Language Program de Arthur Burks , na notação de Heinz Rutishauser , na linguagem e compilador de Corrado Böhm em 1951-1952, no Autocode de Alick Glennie , no sistema A-2 de Grace Hopper , no sistema Laning e Zierler , nos primeiros proposto Fortran (1954) de John Backus , no Autocode para Mark 1 de Tony Brooker , em ПП-2 de Andrey Ershov , em BACAIC de Mandalay Grems e RE Porter, em Kompiler 2 de A. Kenton Elsworth e outros, em ADES de EK Blum, o tradutor interno de Alan Perlis , em Fortran de John Backus, em ARITH-MATIC e MATH-MATIC do laboratório de Grace Hopper , no sistema de Bauer e Samelson , e (em adendos em 2003 e 2009) PACT I e TRANSCODE. Em seguida, descrevem que tipo de aritmética estava disponível e fornecem uma avaliação subjetiva dessas linguagens sobre os parâmetros de "implementação", "legibilidade", "estruturas de controle", "estruturas de dados", "independência da máquina" e "impacto", além de mencionar o que cada um foi o primeiro a fazer.

Implementações em idiomas mais recentes

Implementação C

Isso mostra uma implementação C equivalente ao ALGOL 60 acima.

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

Implementação Python

Isso mostra uma implementação 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)

Implementação de ferrugem

Isso mostra uma implementação 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