Teorema do programa estruturado - Structured program theorem

Representação gráfica dos três padrões básicos do teorema do programa estruturado - sequência, seleção e repetição - usando diagramas NS (azul) e fluxogramas (verde).

O teorema do programa estruturado , também chamado de teorema de Böhm – Jacopini , é um resultado da teoria da linguagem de programação . Ele afirma que uma classe de gráficos de fluxo de controle (historicamente chamados de fluxogramas neste contexto) pode computar qualquer função computável se combinar subprogramas de apenas três maneiras específicas ( estruturas de controle ). Estes são

  1. Executar um subprograma e, em seguida, outro subprograma (sequência)
  2. Execução de um de dois subprogramas de acordo com o valor de uma expressão booleana (seleção)
  3. Executar repetidamente um subprograma, desde que uma expressão booleana seja verdadeira (iteração)

O gráfico estruturado sujeito a essas restrições pode, no entanto, usar variáveis ​​adicionais na forma de bits (armazenadas em uma variável inteira extra na prova original) a fim de manter o controle das informações que o programa original representa pela localização do programa. A construção foi baseada na linguagem de programação P ′ ′ de Böhm .

O teorema forma a base da programação estruturada , um paradigma de programação que evita os comandos goto e usa exclusivamente sub-rotinas, sequências, seleção e iteração.

Origem e variantes

O teorema é normalmente creditado a um artigo de 1966 de Corrado Böhm e Giuseppe Jacopini . David Harel escreveu em 1980 que o artigo Böhm – Jacopini desfrutou de "popularidade universal", particularmente entre os proponentes da programação estruturada. Harel também observou que "devido ao seu estilo bastante técnico [o artigo de Böhm-Jacopini de 1966] é aparentemente mais citado do que lido em detalhes" e, após revisar um grande número de artigos publicados até 1980, Harel argumentou que o conteúdo do A prova de Böhm-Jacopini era geralmente mal representada como um teorema popular que contém essencialmente um resultado mais simples, um resultado que pode ser rastreado até o início da teoria da computação moderna nos artigos de von Neumann e Kleene .

Harel também escreve que o nome mais genérico foi proposto por HD Mills como "O Teorema da Estrutura" no início dos anos 1970.

Versão folk do teorema, single-while-loop

Esta versão do teorema substitui todo o fluxo de controle do programa original por um único whileloop global que simula um contador de programa passando por todos os rótulos possíveis (caixas de fluxograma) no programa não estruturado original. Harel rastreou a origem deste teorema popular em dois artigos que marcam o início da computação. Uma é a descrição de 1946 da arquitetura de von Neumann , que explica como um contador de programa opera em termos de um loop while. Harel observa que o único laço usado pela versão folk do teorema da programação estruturada basicamente fornece semântica operacional para a execução de um fluxograma em um computador de von Neumann. Outra, a fonte ainda mais antiga que Harel traçou a versão popular do teorema é Stephen Kleene de forma teorema normal, de 1936.

Donald Knuth criticou essa forma de prova, que resulta em um pseudocódigo como o abaixo, ao apontar que a estrutura do programa original se perde completamente nessa transformação. Da mesma forma, Bruce Ian Mills escreveu sobre essa abordagem que "O espírito da estrutura de blocos é um estilo, não uma linguagem. Simulando uma máquina Von Neumann, podemos produzir o comportamento de qualquer código espaguete dentro dos limites de uma linguagem estruturada em blocos. Isso não impede que seja espaguete. "

p := 1
while p > 0 do
    if p = 1 then
        perform step 1 from the flowchart
        p := resulting successor step number of step 1 from the flowchart (0 if no successor)
    end if
    if p = 2 then
        perform step 2 from the flowchart
        p := resulting successor step number of step 2 from the flowchart (0 if no successor)
    end if
    ...
    if p = n then
        perform step n from the flowchart
        p := resulting successor step number of step n from the flowchart (0 if no successor)
    end if
end while

Prova de Böhm e Jacopini

A prova no artigo de Böhm e Jacopini procede por indução na estrutura do fluxograma. Por empregar correspondência de padrões em gráficos , a prova de Böhm e Jacopini não era realmente prática como um algoritmo de transformação de programa e, portanto, abriu a porta para pesquisas adicionais nessa direção.

Implicações e refinamentos

A prova de Böhm-Jacopini não resolveu a questão de se adotar ou não a programação estruturada para o desenvolvimento de software, em parte porque a construção tinha mais probabilidade de obscurecer um programa do que de melhorá-lo. Pelo contrário, sinalizou o início do debate. A famosa carta de Edsger Dijkstra , " Go To Statement Considered Harmful ", foi publicada em 1968.

Alguns acadêmicos adotaram uma abordagem purista para o resultado de Böhm – Jacopini e argumentaram que mesmo instruções como breake returndo meio de loops são uma prática ruim, pois não são necessárias na prova de Böhm – Jacopini e, portanto, defenderam que todos os loops deveriam ter um único ponto de saída. Essa abordagem purista está incorporada na linguagem de programação Pascal (desenvolvida em 1968–1969), que até meados da década de 1990 era a ferramenta preferida para o ensino de aulas introdutórias de programação na academia.

Edward Yourdon observa que na década de 1970 havia até mesmo oposição filosófica à transformação de programas não estruturados em estruturados por meios automatizados, com base no argumento de que era necessário pensar em programação estruturada desde o início. O contraponto pragmático foi que tais transformações beneficiaram um grande corpo de programas existentes. Entre as primeiras propostas para uma transformação automatizada estava um artigo de 1971 de Edward Ashcroft e Zohar Manna .

A aplicação direta do teorema de Böhm – Jacopini pode resultar em variáveis ​​locais adicionais sendo introduzidas no gráfico estruturado e também pode resultar em alguma duplicação de código . O último problema é chamado de problema de loop e meio neste contexto. Pascal é afetado por esses dois problemas e, de acordo com estudos empíricos citados por Eric S. Roberts , os alunos programadores tiveram dificuldade em formular soluções corretas em Pascal para vários problemas simples, incluindo escrever uma função para pesquisar um elemento em um array. Um estudo de 1980 por Henry Shapiro citado por Roberts descobriu que usando apenas as estruturas de controle fornecidas por Pascal, a solução correta foi dada por apenas 20% dos sujeitos, enquanto nenhum sujeito escreveu um código incorreto para este problema se permitido escrever um retorno do meio de um loop.

Em 1973, S. Rao Kosaraju provou que é possível evitar a adição de variáveis ​​adicionais na programação estruturada, desde que sejam permitidas quebras de loops de vários níveis e profundidade arbitrária. Além disso, Kosaraju provou que existe uma hierarquia estrita de programas, hoje chamada de hierarquia Kosaraju , em que para cada inteiro n , existe um programa contendo uma quebra multinível de profundidade n que não pode ser reescrita como programa com quebras multinível de profundidade menor que n (sem introdução de variáveis ​​adicionais). Kosaraju cita a construção de quebra de vários níveis para a linguagem de programação BLISS . As quebras de vários níveis, na forma de uma palavra - chave, foram realmente introduzidas na versão BLISS-11 desse idioma; o BLISS original só tinha quebras de nível único. A família de idiomas BLISS não forneceu um goto irrestrito. A linguagem de programação Java viria a seguir esta abordagem também. leave label

Um resultado mais simples do artigo de Kosaraju é que um programa é redutível a um programa estruturado (sem adicionar variáveis) se e somente se ele não contiver um loop com duas saídas distintas. A redutibilidade foi definida por Kosaraju, falando livremente, como computar a mesma função e usar as mesmas "ações primitivas" e predicados do programa original, mas possivelmente usando diferentes estruturas de fluxo de controle. (Esta é uma noção mais restrita de redutibilidade do que a que Böhm – Jacopini usou.) Inspirado por este resultado, na seção VI de seu artigo altamente citado que introduziu a noção de complexidade ciclomática , Thomas J. McCabe descreveu um análogo do teorema de Kuratowski para o gráficos de fluxo de controle (CFG) de programas não estruturados, ou seja, os subgráficos mínimos que tornam o CFG de um programa não estruturado. Esses subgráficos têm uma descrição muito boa em linguagem natural. Eles são:

  1. ramificação de um loop (diferente do teste de ciclo do loop)
  2. ramificando em um loop
  3. ramificação em uma decisão (ou seja, em uma "ramificação" if)
  4. ramificação de uma decisão

McCabe realmente descobriu que esses quatro gráficos não são independentes quando aparecem como subgráficos, o que significa que uma condição necessária e suficiente para um programa ser não estruturado é que seu CFG tenha como subgráfico um de qualquer subconjunto de três desses quatro gráficos. Ele também descobriu que se um programa não estruturado contém um desses quatro subgráficos, ele deve conter outro diferente do conjunto de quatro. Este último resultado ajuda a explicar como o fluxo de controle de um programa não estruturado fica emaranhado no que é popularmente chamado de " código espaguete ". McCabe também concebeu uma medida numérica que, dado um programa arbitrário, quantifica o quão longe está do ideal de ser um programa estruturado; McCabe chamou sua medida de complexidade essencial .

A caracterização de McCabe dos grafos proibidos para programação estruturada pode ser considerada incompleta, pelo menos se as estruturas D de Dijkstra forem consideradas os blocos de construção.

Até 1990, havia alguns métodos propostos para eliminar os gotos de programas existentes, preservando a maior parte de sua estrutura. As várias abordagens para este problema também propuseram várias noções de equivalência, que são mais rígidas do que simplesmente a equivalência de Turing, a fim de evitar saídas como o teorema folk discutido acima. O rigor da noção escolhida de equivalência dita o conjunto mínimo de estruturas de fluxo de controle necessárias. O artigo JACM de 1988, de Lyle Ramshaw, faz um levantamento do campo até aquele ponto, além de propor seu próprio método. O algoritmo de Ramshaw foi usado, por exemplo, em alguns descompiladores Java porque o código da máquina virtual Java tem instruções de ramificação com destinos expressos como deslocamentos, mas a linguagem Java de alto nível possui apenas vários níveis breake continueinstruções. Ammarguellat (1992) propôs um método de transformação que volta a impor uma saída única.

Aplicativo para Cobol

Na década de 1980, o pesquisador da IBM Harlan Mills supervisionou o desenvolvimento do COBOL Structuring Facility , que aplicou um algoritmo de estruturação ao código COBOL . A transformação de Mills envolveu as seguintes etapas para cada procedimento.

  1. Identifique os bloqueios básicos do procedimento.
  2. Atribua um rótulo exclusivo ao caminho de entrada de cada bloco e rotule os caminhos de saída de cada bloco com os rótulos dos caminhos de entrada aos quais eles se conectam. Use 0 para retornar do procedimento e 1 para o caminho de entrada do procedimento.
  3. Divida o procedimento em seus blocos básicos.
  4. Para cada bloco que é o destino de apenas um caminho de saída, reconecte esse bloco a esse caminho de saída.
  5. Declare uma nova variável no procedimento (chamada de L para referência).
  6. Em cada caminho de saída não conectado restante, adicione uma instrução que defina L como o valor do rótulo nesse caminho.
  7. Combine os programas resultantes em uma instrução de seleção que executa o programa com o rótulo do caminho de entrada indicado por L
  8. Construa um loop que execute esta instrução de seleção, desde que L não seja 0.
  9. Construa uma sequência que inicialize L em 1 e execute o loop.

Observe que esta construção pode ser melhorada convertendo alguns casos da instrução de seleção em subprocedimentos.

Veja também

Referências

Leitura adicional

Material ainda não coberto acima: