BlooP e FlooP - BlooP and FlooP
BlooP e FlooP são linguagens de programação simples projetadas por Douglas Hofstadter para ilustrar um ponto em seu livro Gödel, Escher, Bach . BlooP é uma linguagem de programação não completa de Turing cuja estrutura de fluxo de controle principal é um loop limitado (ou seja, a recursão não é permitida). Todos os programas da linguagem devem terminar, e esta linguagem pode expressar apenas funções recursivas primitivas .
O FlooP é idêntico ao BlooP, exceto que ele suporta loops ilimitados; é uma linguagem Turing completa e pode expressar todas as funções computáveis . Por exemplo, pode expressar a função de Ackermann , que (não sendo recursiva primitiva) não pode ser escrita em BlooP. Pegando emprestado a terminologia padrão em lógica matemática , Hofstadter chama os loops ilimitados do FlooP de MU-loops. Como todas as linguagens de programação Turing-complete, o FlooP sofre do problema da parada : os programas podem não terminar e não é possível, em geral, decidir quais programas terminam.
BlooP e FlooP podem ser considerados modelos de computação e algumas vezes têm sido usados no ensino de computabilidade.
Exemplos de BlooP
As únicas variáveis são OUTPUT (o valor de retorno do procedimento) e (uma sequência ilimitada de variáveis de número natural, indexada por constantes, como na Máquina de Registro Ilimitada ). Os únicos operadores são ( atribuição ), (adição), (multiplicação), (menor que), (maior que) e (igual).
CELL(i)⇐+×<>=
Cada programa usa apenas um número finito de células, mas os números nas células podem ser arbitrariamente grandes. Estruturas de dados, como listas ou pilhas, podem ser manipuladas interpretando o número em uma célula de maneiras específicas, ou seja, por Gödel numerando as estruturas possíveis.
As construções de fluxo de controle incluem loops limitados, declarações condicionais , ABORT saltos de loops e QUIT saltos de blocos. O BlooP não permite recursão, saltos irrestritos ou qualquer outra coisa que tenha o mesmo efeito que os loops ilimitados do FlooP. Os procedimentos nomeados podem ser definidos, mas só podem chamar procedimentos definidos anteriormente.
Função fatorial
DEFINIR PROCEDIMENTO FACTORIAL [N]:
BLOCO 0: BEGIN
OUTPUT ⇐ 1;
CELL (0) ⇐ 1;
LOOP NA MAIORIA DE N VEZES:
BLOCO 1: COMEÇAR
SAÍDA ⇐ SAÍDA × CÉLULA (0);
CÉLULA (0) ⇐ CÉLULA (0) + 1;
BLOCO 1: FIM;
BLOCO 0: END.
Função de subtração
Esta não é uma operação embutida e (sendo definida em números naturais) nunca dá um resultado negativo (por exemplo, 2 - 3: = 0). Observe que OUTPUT começa em 0, como todos os se CELL , portanto, não requer inicialização.
DEFINIR PROCEDIMENTO MENOS [M, N]:
BLOCO 0: BEGIN
SE M <N, ENTÃO:
QUIT BLOCK 0;
LOOP NA MAIORIA DE M + 1 VEZES:
BLOCO 1: COMEÇAR
SE SAÍDA + N = M, ENTÃO:
ABORT LOOP 1;
OUTPUT ⇐ OUTPUT + 1;
BLOCO 1: FIM;
BLOCO 0: END.
Exemplo FlooP
O exemplo a seguir, que implementa a função de Ackermann , depende de simular uma pilha usando a numeração Gödel : que é, em funções numéricas anteriormente definidos PUSH , POP e TOP satisfazendo PUSH [N, S] > 0 , TOP [PUSH [N, S]] = N , e POP [PUSH [N, S]] = S . Como um ilimitado MU-LOOP é usado, este não é um programa BlooP legal. As QUIT BLOCK instruções, neste caso, saltam para o final do bloco e repetem o loop, ao contrário de ABORT , que sai do loop.
DEFINIR PROCEDIMENTO ACKERMANN [M, N]: BLOCO 0: BEGIN CÉLULA (0) ⇐ M; OUTPUT ⇐ N; CELL (1) ⇐ 0; MU-LOOP: BLOCO 1: COMEÇAR SE CÉLULA (0) = 0, ENTÃO: BLOCO 2: COMEÇAR OUTPUT ⇐ OUTPUT + 1; SE CÉLULA (1) = 0, ENTÃO: ABORTAR O LOOP 1; CÉLULA (0) ⇐ SUPERIOR [CÉLULA (1)]; CÉLULA (1) ⇐ POP [CÉLULA (1)]; SAIR DO BLOCO 1; BLOCO 2: FIM SE SAÍDA = 0, ENTÃO: BLOCO 3: COMEÇAR OUTPUT ⇐ 1; CÉLULA (0) ⇐ MENOS [CÉLULA (0), 1]; SAIR DO BLOCO 1; BLOCO 3: FIM SAÍDA ⇐ MENOS [SAÍDA, 1]; CÉLULA (1) ⇐ PUSH [MENOS [CÉLULA (0), 1], CÉLULA (1)]; BLOCO 1: FIM; BLOCO 0: END.