Teorema do programa estruturado

Teorema do programa estruturado 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,[1][2] é um resultado na 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 calcular qualquer função computável se combinar subprogramas de apenas três maneiras específicas (estruturas de controle). These are Executing one subprogram, e depois outro subprograma (seqüência) Executando um dos dois subprogramas de acordo com o valor de uma expressão booleana (seleção) Executando repetidamente um subprograma enquanto uma expressão booleana for verdadeira (iteração) O gráfico estruturado sujeito a essas restrições pode, no entanto, usar variáveis ​​adicionais na forma de bits (armazenado em uma variável inteira extra na prova original) para acompanhar as 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 comandos goto e usa exclusivamente sub-rotinas, sequências, seleção e iteração.

Conteúdo 1 Origem e variantes 1.1 Ciclo único, versão popular do teorema 1.2 A prova de Böhm e Jacopini 2 Implicações e refinamentos 3 Aplicativo para Cobol 4 Veja também 5 Referências 6 Further reading Origin and variants The theorem is typically credited[3]:381  para um 1966 artigo de Corrado Böhm e Giuseppe Jacopini.[4] David Harel escreveu em 1980 que o jornal Böhm-Jacopini apreciou "popularidade universal",[3]:381  particularmente com os defensores da programação estruturada. Harel também observou que "devido ao seu estilo bastante técnico [a 1966 papel Boehm-Jacopini] é aparentemente mais citado do que lido em detalhes"[3]:381  e, após revisar um grande número de artigos publicados até 1980, Harel argumentou que o conteúdo da prova de Böhm-Jacopini era geralmente deturpado como um teorema popular que essencialmente contém um resultado mais simples, um resultado que pode ser atribuído ao início da teoria da computação moderna nos artigos de von Neumann e Kleene.[3]: 383  Harel also writes that the more generic name was proposed by H.D. Moinhos como "O Teorema da Estrutura" no início dos anos 1970.[3]: 381  Single-while-loop, folk version of the theorem This version of the theorem replaces all the original program's control flow with a single global while loop that simulates a program counter going over all possible labels (caixas de fluxograma) no programa não estruturado original. Harel traçou a origem deste teorema popular em dois artigos que marcam o início da computação. Um é o 1946 descrição da arquitetura von Neumann, que explica como um contador de programa opera em termos de um loop while. Harel observa que o loop único usado pela versão popular do teorema da programação estruturada basicamente fornece semântica operacional para a execução de um fluxograma em um computador de von Neumann.[3]:383  Outro, fonte ainda mais antiga que Harel traçou a versão popular do teorema é o teorema da forma normal de Stephen Kleene de 1936.[3]: 383  Donald Knuth criticized this form of the proof, que resulta em pseudocódigo como o abaixo, apontando que a estrutura do programa original se perde completamente nessa transformação.[5]:274  Da mesma forma, Bruce Ian Mills escreveu sobre essa abordagem que "O espírito da estrutura de blocos é um estilo, não é um idioma. Ao simular uma máquina de 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."[6] p := 1 while p > 0 do if p = 1 then perform step 1 from the flowchart p := número do passo sucessor resultante do passo 1 do fluxograma (0 se não houver sucessor) end if if p = 2 then perform step 2 from the flowchart p := número do passo sucessor resultante do passo 2 do fluxograma (0 se não houver sucessor) fim se ...

if p = n then perform step n from the flowchart p := número da etapa sucessora resultante da etapa n do fluxograma (0 se não houver sucessor) end if end while Böhm and Jacopini's proof This section needs expansion. Você pode ajudar expandindo-o. (Julho 2014) A prova no artigo de Böhm e Jacopini procede por indução na estrutura do fluxograma.[3]:381  Porque empregou 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, assim, abriu a porta para pesquisas adicionais nessa direção.[7] Implications and refinements The Böhm–Jacopini proof did not settle the question of whether to adopt structured programming for software development, em parte porque a construção era mais propensa a obscurecer um programa do que a melhorá-lo. Pelo contrário, marcou o início do debate. A famosa carta de Edsger Dijkstra, "Ir para declaração considerada prejudicial," seguido em 1968.[8] Alguns acadêmicos adotaram uma abordagem purista para o resultado de Böhm-Jacopini e argumentaram que mesmo instruções como break e return do meio de loops são uma má prática, pois não são necessárias na prova de Böhm-Jacopini, e assim eles defenderam que todos os loops deveriam ter um único ponto de saída. Esta abordagem purista está incorporada na linguagem de programação Pascal (projetado 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.[9] 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, baseado no argumento de que era preciso pensar em programação estruturada desde o início. O contraponto pragmático foi que tais transformações beneficiaram grande parte dos programas existentes.[10] Entre as primeiras propostas para uma transformação automatizada estava uma 1971 papel de Edward Ashcroft e Zohar Manna.[11] A aplicação direta do teorema de Böhm–Jacopini pode resultar na introdução de variáveis ​​locais adicionais no gráfico estruturado, e também pode resultar em alguma duplicação de código.[12] A última questão é chamada de problema de loop e meio neste contexto.[13] Pascal é afetado por ambos os problemas e de acordo com estudos empíricos citados por Eric S. Roberts, estudantes 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 uma matriz. UMA 1980 estudo de Henry Shapiro citado por Roberts descobriu que usar apenas as estruturas de controle fornecidas por Pascal, a solução correta foi dada por apenas 20% dos assuntos, enquanto nenhum assunto escreveu código incorreto para este problema se permitido escrever um retorno do meio de um loop.[9] Dentro 1973, S. Rao Kosaraju provou que é possível evitar adicionar variáveis ​​adicionais na programação estruturada, enquanto profundidade arbitrária, quebras de vários níveis de loops são permitidas.[1][14] Além disso, Kosaraju provou que existe uma hierarquia estrita de programas, hoje chamada de hierarquia Kosaraju, em que para todo inteiro n, existe um programa contendo uma quebra multinível de profundidade n que não pode ser reescrita como um programa com quebra multinível de profundidade menor que n (sem introduzir variáveis ​​adicionais).[1] Kosaraju cita a construção de quebra multinível para a linguagem de programação BLISS. As quebras de vários níveis, na forma de uma palavra-chave de rótulo de licença foram realmente introduzidas na versão BLISS-11 desse idioma; o BLISS original tinha apenas quebras de nível único. A família de idiomas BLISS não fornecia um acesso irrestrito. A linguagem de programação Java mais tarde também seguiria essa abordagem.[15]: 960–965  A simpler result from Kosaraju's paper is that a program is reducible to a structured program (sem adicionar variáveis) se e somente se não contiver um loop com duas saídas distintas. A redutibilidade foi definida por Kosaraju, falando livremente, como computando a mesma função e usando o mesmo "ações primitivas" e predicados como o programa original, mas possivelmente usando diferentes estruturas de fluxo de controle. (Esta é uma noção mais restrita de redutibilidade do 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 os gráficos de fluxo de controle (CFG) de programas não estruturados, o que quer dizer, os subgrafos mínimos que fazem o CFG de um programa não estruturado. Esses subgráficos têm uma descrição muito boa em linguagem natural. Eles são: ramificação de um loop (além do teste de ciclo de loop) ramificação em um loop ramificação em uma decisão (ou seja. em um se "ramo") branching out of a decision McCabe actually found that these four graphs are not independent when appearing as subgraphs, significando que uma condição necessária e suficiente para um programa não ser estruturado é que seu CFG tenha como subgrafo um de qualquer subconjunto de três desses quatro gráficos. Ele também descobriu que se um programa não estruturado contiver um desses quatro subgráficos, deve conter outro distinto do conjunto de quatro. Este último resultado ajuda a explicar como o fluxo de controle de programas não estruturados fica enredado no que é popularmente chamado de "código de espaguete". McCabe também desenvolveu 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.[16] A caracterização de McCabe dos grafos proibidos para programação estruturada pode ser considerada incompleta, pelo menos se as estruturas D da Dijkstra forem consideradas os blocos de construção.[17]:274–275[esclarecimento necessário] Até 1990 havia alguns métodos propostos para eliminar 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 estritas do que simplesmente equivalência de Turing, para evitar saídas como o teorema popular discutido acima. O rigor da noção de equivalência escolhida dita o conjunto mínimo de estruturas de fluxo de controle necessárias. o 1988 O artigo JACM de Lyle Ramshaw examina o campo até aquele ponto, bem como propondo seu próprio método.[18] O algoritmo de Ramshaw foi usado, por exemplo, em alguns descompiladores Java porque o código da máquina virtual Java possui instruções de ramificação com destinos expressos como deslocamentos, mas a linguagem Java de alto nível tem apenas instruções break e continue de vários níveis.[19][20][21] Ele desmaia (1992) propôs um método de transformação que volta a impor a saída única.[7] Application to Cobol This section needs additional citations for verification. Ajude a melhorar este artigo adicionando citações a fontes confiáveis. O material sem fonte pode ser contestado e removido. (Agosto 2013) (Saiba como e quando remover esta mensagem de modelo) 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.

Identifique os blocos básicos no procedimento. 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. Usar 0 para retorno do procedimento e 1 para o caminho de entrada do procedimento. Divida o procedimento em seus blocos básicos. Para cada bloco que é destino de apenas um caminho de saída, reconecte esse bloco a esse caminho de saída. Declare uma nova variável no procedimento (chamado L para referência). Em cada caminho de saída desconectado restante, adicione uma instrução que defina L para o valor do rótulo nesse caminho. Combine os programas resultantes em uma instrução de seleção que execute o programa com o rótulo do caminho de entrada indicado por L Construa um loop que execute essa instrução de seleção enquanto L não for 0. Construa uma sequência que inicialize L para 1 e executa o loop.

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

Veja também Programação estruturada Completude de Turing Referências ^ Saltar para: a b c Dexter Kozen e Wei-Lung Dustin Tseng (2008). O teorema de Böhm-Jacopini é falso, Proposicionalmente (PDF). MPC 2008. Notas de aula em Ciência da Computação. Volume. 5133. pp. 177-192. CiteSeerX 10.1.1.218.9241. doi:10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70593-2. ^ "CSE 111, Cair 2004, TEOREMA DE BOEHM-JACOPINI". Cse.buffalo.edu. 2004-11-22. Recuperado 2013-08-24. ^ Saltar para: a b c d e f g h Harel, Davi (1980). "Sobre teoremas populares" (PDF). Comunicações da ACM. 23 (7): 379-389. doi:10.1145/358886.358892. S2CID 16300625. ^ Bohm, Corrado; Giuseppe Jacopini (Poderia 1966). "Diagramas de fluxo, Máquinas de Turing e Linguagens com Apenas Duas Regras de Formação". Comunicações da ACM. 9 (5): 366-371. CiteSeerX 10.1.1.119.9119. doi:10.1145/355592.365646. S2CID 10236439. ^ Donald Knuth (1974). "Programação estruturada com instruções go to". Pesquisas de computação. 6 (4): 261-301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080. ^ Bruce Ian Mills (2005). Introdução Teórica à Programação. Springer. p. 279. ISBN 978-1-84628-263-8. ^ Saltar para: a b Amarguellat, Z. (1992). "Um algoritmo de normalização de fluxo de controle e sua complexidade". Transações IEEE em Engenharia de Software. 18 (3): 237-251. doi:10.1109/32.126773. ^ Dijkstra, Edsger (1968). "Ir para declaração considerada prejudicial". Comunicações da ACM. 11 (3): 147-148. doi:10.1145/362929.362947. S2CID 17469809. Arquivado a partir do original em 2007-07-03. ^ Saltar para: a b Roberts, E. [1995] "Saídas de loop e programação estruturada: Reabrindo o Debate," Boletim ACM SIGCSE, (27)1: 268-272. ^ E. N. Yourdon (1979). Clássicos em Engenharia de Software. Yourdon Press. pp. 49-50. ISBN 978-0-917072-14-7. ^ Ashcroft, Eduardo; Zohar Maná (1971). "A tradução de ir para programas para programas 'enquanto'". Anais do Congresso IFIP. O papel, que é difícil de obter nos anais originais da conferência devido à sua distribuição limitada, foi republicado em Yourdon's 1979 livro pp. 51-65 ^ David Anthony Watt; William Findlay (2004). Conceitos de design de linguagem de programação. John Wiley & Sons. p. 228. ISBN 978-0-470-85320-7. ^ Kenneth C. alto; Kenneth A. Lambert (2011). Linguagens de programação: Princípios e Práticas (3 ed.). Cengage Learning. pp. 422-423. ISBN 978-1-111-52941-3. ^ BASQUETEBOL, S. RAO. "Análise de programas estruturados," Proc. Quinto Xarope Anual ACM. Teoria da Computação, (Poderia 1973), 240-252; também Kosaraju, S. Rao (1974). "Análise de programas estruturados". Revista de Ciências da Computação e Sistemas. 9 (3): 232-255. doi:10.1016/S0022-0000(74)80043-7. citado por Donald Knuth (1974). "Programação estruturada com instruções go to". Pesquisas de computação. 6 (4): 261-301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080. ^ Brender, Ronaldo F. (2002). "A linguagem de programação BLISS: uma história" (PDF). Programas: Prática e experiência. 32 (10): 955–981. doi:10.1002/espec.470. S2CID 45466625. ↑ O artigo original é Thomas J. McCabe (dezembro 1976). "Uma medida de complexidade". Transações IEEE em Engenharia de Software. SE-2 (4): 315-318. doi:10.1109/estes.1976.233837. S2CID 9116234. Para uma exposição secundária ver Paul C. Jorgensen (2002). Teste de software: Abordagem de um artesão, Segunda edição (2ª edição). Imprensa CRC. pp. 150–153. ISBN 978-0-8493-0809-3. ^ Williams, M. H. (1983). "Esquema de fluxograma e o problema da nomenclatura". O Diário do Computador. 26 (3): 270-276. doi:10.1093/comjnl/26.3.270. ^ Ramshaw, eu. (1988). "Eliminando go to's preservando a estrutura do programa". Jornal da ACM. 35 (4): 893-920. doi:10.1145/48014.48021. S2CID 31001665. ^ Godfrey Nolan (2004). Descompilando Java. Apress. p. 142. ISBN 978-1-4302-0739-9. ^ https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf[URL simples PDF] ^ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf[URL simples PDF] Further reading Material not yet covered above: DeMillo, Ricardo A. (1980). "Trade-offs espaço-tempo na programação estruturada: Um Teorema de Incorporação Combinatória Aprimorado". Jornal da ACM. 27 (1): 123-127. doi:10.1145/322169.322180. S2CID 15669719. Vir a ser, Filipe (1994). "Uma cláusula de chifre binário é suficiente". Pilhas 94. Notas de aula em Ciência da Computação. Volume. 775. pp. 19-32. CiteSeerX 10.1.1.14.537. doi:10.1007/3-540-57785-8_128. ISBN 978-3-540-57785-0. Categorias: Teoria da linguagem de programaçãoModelos de computaçãoTeoremas na teoria da complexidade computacional