Versão 0.4 Capítulo 3 Algoritmos e linguagens de programação Um

Versão 0.4 Capítulo 3 Algoritmos e linguagens de programação Um computador é projetado de tal forma que pode desempenhar funções que sequer foram imaginadas quando da época de sua concepção. Mas, para isso, é preciso que um programa seja nele instalado para que possa ser executado. Como vimos nos capítulos anteriores, tudo que o computador executa deve ser feito por circuitos eletrônicos digitais, cujas instruções têm que necessariamente ser expressas em termos de zeros e uns. Para introduzir os conceitos de linguagens de programação iremos simplificar ainda mais uma linguagem de programação que foi desenvolvida com o propósito de ensinar programação em “linguagem de máquina”, que é o nível mais próximo da linguagem que o processador “entende”, que é de zeros e uns. Usaremos a linguagem Hipo (de computador HIPOtético), desenvolvida pelo Prof Valdemar Setzer, a partir de um sub-­‐conjunto das instruções de um computador real (IBM 1620, fabricado na década de 1960, Setzer, 2000). Imaginem que cada instrução corresponda a uma parte de um circuito eletrônico como mostrado no capítulo anterior. Assim, um programa é uma série de instruções. Instruções do computador eletrônico digital Hipo Núm. Mnemônico O que é executado e sintaxe Copia o conteúdo da memória localizada no endereço NN 11 LDA NN 12 STA NN 21 ADD NN 22 SUB NN 23 MUL NN 24 DIV NN 25 REM NN 29 31 REV INN NN 41 PRN NN 50 51 NOP JMP NN 52 JLE NN 53 JDZ NN 54 JGT NN 55 JEQ NN 56 JLT NN 57 JGT NN 58 JGE NN 70 STP para o acumulador. Copia o conteúdo do acumulador para a memória localizada no endereço NN. Adiciona o conteúdo da memória de endereço NN com o conteúdo do acumulador e grava o resultado no acumulador. Subtrai o conteúdo da memória de endereço NN do conteúdo do acumulador e grava o resultado no acumulador Multiplica o conteúdo da memória de endereço NN pelo conteúdo do acumulador e coloca o resultado no acumulador Divide o conteúdo da memória de endereço NN pelo acumulador e coloca o resultado no acumulador Divide o conteúdo da memória de endereço NN pelo acumulador e coloca o resto da divisão no acumulador. Muda o sinal do conteúdo do acumulador. Lê um número que foi digitado do teclado e o guarda no endereço NN da memória. Imprima a representação decimal do conteúdo da memória com endereço NN. Não executa operação alguma. Muda a posição da instrução corrente para a posição NN incondicionalmente. Muda a posição da instrução corrente para a posição NN se o valor armazenado no acumulador for menor ou igual a zero. Muda a posição da instrução corrente para a posição NN se o valor armazenado no acumulador for diferente de zero. Muda a posição da instrução corrente para a posição NN se o valor armazenado no acumulador for maior que zero. Muda a posição da instrução corrente para a posição NN se o valor armazenado no acumulador for igual a zero. Muda a posição da instrução corrente para a posição NN se o valor armazenado no acumulador for menor que zero. Muda a posição da instrução corrente para a posição NN se o valor armazenado no acumulador for menor que zero. Muda a posição da instrução corrente para a posição NN se o valor armazenado no acumulador for menor que zero. Interrompe a execução do programa. Um programa que lê, no teclado, o valor de dois números e apresenta a sua soma no dispositivo de saída seria escrito assim, de acordo com a linguagem de programação simplificada acima: 010 INN 77
020 INN 78
030 LDA 77
040 ADD 78
050 STA 78
060 PRN 78
070 STP 00
Para cada instrução há três valores (instruções que não se referem a um endereço são preenchidas com 00). O primeiro valor (obrigatório) é número de ordem da instrução. Os números de ordem não precisam ser sequenciais (como 21,22,23, etc.) mas as instruções serão executadas na ordem crescente a menos que uma instrução de controle de fluxo (desvio) seja executada. Lembrem-­‐se que essa linguagem é da época de cartões perfurados, a numeração dos cartões eram muito úteis, por exemplo, quando acidentalmente eles se espalhavam ao cair no chão... O número a seguir é aquele correspondente à instrução. O terceiro valor é o endereço da memória que é acessado (gravado ou recuperado) durante a instrução executada. Evidentemente o computador não entenderia essas instruções, mas sim aquelas correspondentes aos números binários dessas instruções. Assim, na primeira linha o primeiro valor seria 1010 (10 decimal, ignoraremos os zeros à esquerda), o segundo seria 11111 (31 decimal, que corresponde à instrução INN) e o terceiro seria 1001101 (77 decimal, endereço da memória escolhido). Assim, em binário, completando os zeros à esquerda para termos 1 byte de informação para cada valor, o programa quase inteligível para uma máquina seria: 00001010
00011111 01001101
00010100
00011111 01001101
00011110
00001011 01001110
00101000
00010101 01001110
00110010
00001011 01001110
00111100
00101001 01001110
01000110
01000110 00000000
Mas os bits acima estão organizados em blocos de 8 bits acima, como o processador já sub-­‐entende isso, o programa eletronicamente viável seria: 0000101000011111010011010001010000011111010011010001
1110000010110100111000101000000101010100111000110010000010110
1001110001111000010100101001110010001100100011000000000
Essa é a verdadeira “linguagem de máquina”, algo que nós, humanos temos muita dificuldade em entender em termos do que o computador faz com essas instruções, a menos que você seja um engenheiro eletrônico muito NERD. As linguagens de programação podem ser classificadas em níveis. A série de zeros e uns acima, que é a única linguagem que o computador realmente entende, está no nível mais baixo. Existem, felizmente, linguagens de níveis mais alto, mais distantes portanto da “linguagem de máquina” e mais próximas da linguagem humana. Aquilo que nós podemos fazer “manualmente”, que foi a transformação do código com mnemônicos (assembler) em binário (tabela 1) Tabela 1. Correspondência de instruções em assembler para linguagem de máquina. Linguagem de máquina
Código assembler 01001101
010 INN 77 00001010 00011111
01001101
020 INN 78 00010100 00011111
01001110
030 LDA 77 00011110 00001011
01001110
040 ADD 78 00101000 00010101
01001110
050 STA 78 00110010 00001011
01001110
060 PRN 78 00111100 00101001
00000000
070 STP 00 01000110 01000110
Essa operação, embora muito fácil, é muito mais que entediante e sujeita a erros dificílimos de serem percebidos posteriormente sem uma verificação incrivelmente maçante. Felizmente, essa tarefa é desempenhada por programas, conhecidos como compiladores ou interpretadores assembler, que fazem a transformação automática do programa escrito em assembler para a linguagem de máquina. Algoritmos Algoritmos podem ser considerados como conjuntos de procedimentos logicamente encadeados que servem para executar tarefas. Nós emitimos e recebemos ordens para realizar tarefas. Por exemplo, uma mãe pode solicitar aos filhos que arrumem as suas camas depois que levantarem. Essa mãe se expressa em uma linguagem de alto nível, pois “arrumar a cama” implica uma série de procedimentos mais simples que poderiam ser assim descritos: 1. Comece a arrumar a cama. 2. Verifique se a cama está arrumada. Sim: Encerre a sua atividade; comunique ã sua mãe: “Mãe, terminei!”; Vá para o passo 8. Não: Continue no passo 3. 3. Verifique se o elemento [fronha],[cobertor],[travesseiro],[lençóis] está sujo: Sim: Coloque o elemento sujo no saco de lavanderia; pegue um limpo. Não: Tire o elemento da cama; Verifique o próximo elemento. 4. O elemento era o último da lista? Sim: Vá para a instrução 5. Não: Volte para a instrução 3 e mude para o próximo elemento. 5. Coloque adequadamente os elementos na cama [lençol 1], [travesseiro], [fronha], [lençol 2], [cobertor] 6. O elemento era o último da lista? Sim: Vá para a instrução 2. Não: Volte para a instrução 5 e mude para o próximo elemento. 8. Término da tarefa. Se refletirmos mais profundamente, mesmo cada uma dessas instruções são emitidas em um nível muito alto. Aquilo que seria equivalente, em linguagem de máquina de computador, para instruções executadas por nós seria a intensidade e a duração de cada contração de cada um dos músculos de nosso corpo, em função da informação colhida por células táteis, pressoceptoras, receptoras da retina, receptoras de sons da cóclea e de equilíbrio da orelha interna, etc. Assim, existe algo em nosso sistema nervoso que faz o papel de interpretador e/ou compilador mas que não pertence ao domínio de nossa consciência. Fluxogramas Uma das maneiras de facilitar o entendimento e a implementação de um algoritmo é a confecção de fluxogramas. Os fluxogramas evidenciam a estrutura do algoritmo considerado. Alguns símbolos usados em fluxogramas estão mostrados na figura 1. Figura 1. Símbolos usados em fluxogramas e seu significado Figura 2. Exemplo de fluxograma com o algoritmo “arrume a cama”. Linguagens interpretadas e linguagens compiladas Os códigos de nível mais alto do que a linguagem de máquina, como vimos, para serem executados, precisam primeiro ser transformados em zeros e uns. Isso pode ser feito de duas maneiras, através de programas interpretadores e através de programas compiladores. Com o emprego de programas interpretadores, o código de alto nível é transformado em linguagem de máquina, linha a linha, durante o próprio processamento. Os compiladores fazem essa transformação antes do processamento, tudo de uma vez. A vantagem dos programas compilados é que são ligeiramente mais rápidos e não necessitam da presença, na memória, do programa interpretador. Os programas compilados, no entanto, são completamente ininteligíveis e tornam a tarefa de encontrar erros em tempo de processamento muito mais difícil. Breve histórico das linguagens de programação. Antes que os programas fossem armazenados na memória, os computadores eram programados pela modificação na posição de fios que interconectam os circuitos eletrônicos. Na figura 3, parte de um computador da década de 1940 mostrando os painéis de mudança de fiação. Assim, um computador que tivesse uma determinada combinação de fios interligados serviria para executar um tipo de tarefa somente. Figura 3. Painéis de mudança de fiação do computador ENIAC (circa 1950). Fotografia cortesia das forças armadas norte-­‐americanas (domínio público). A primeira linguagem de nível maior que o assembler de uso disseminado foi a linguagem FORTRAN, elaborada em 1944. O nome se origina da contração dos sufixos de formula e de translation, algo como “tradutor de fórmulas”. Essa linguagem, em suas primeiras versões, admitia que os programas eram para ser escritos em cartões perfurados de 80 colunas. As primeiras 6 colunas eram reservadas para numeração das linhas de código, onde fosse necessário. A sétima coluna era reservada para continuação de linhas que precisassem ultrapassar os espaços disponíveis de um único cartão. As instruções eram escritas da 8a até a 72a coluna. Os comentários (que não são levados em consideração durante a execução), são extremamente úteis para as pessoas entenderem o que o programa executa em cada momento, seja por pessoas que não foram os criadores do programa, seja pelo próprio programador, que facilmente pode se esquecer do que ele pretendia com aquelas instruções após certo tempo. Os comentários obrigatoriamente iniciavam-­‐se com a letra “C” (de “comment”) na primeira coluna. C
C
C
C
AREA DE UM TRIANGULO – FORMULA DE HERON
ENTRADA – LEITOR DE CARTOES UNIDADE 5, NUMEROS INTEIROS
SAIDA – IMPRESSORA UNIDADE 6, REAL SAIDA NUMERO INTEIRO
INPUT ERROR DISPAY ERROR OUTPUT CODE 1 IN JOB CONTROL LISTING
INTEGER A,B,C
READ(5,501) A,B,C
501 FORMAT(3I5)
IF(A.EQ.0 .OR. B.EQ.0 .OR. C.EQ.0) STOP 1
S = (A + B + C) / 2.0
AREA = SQRT( S * (S - A) * (S - B) * (S - C))
WRITE(6,601) AREA
601 FORMAT(4H AREA= ,F10.2,12HSQUARE UNITS)
STOP
END
Figura 4. Exemplo de um programa em FORTRAN que calcula a área de um triângulo a partir da informação do comprimento de seus lados. O valor de cada um dos lados foi armazenado nas posições denominadas “A”, “B” e “C”. Note qua nesse programa não há necessidade de se lidar com endereços de memória, o compilador fará essa tarefa. O comando “IF” verifica se algum dos lados tem valor zero e interrompe o programa caso houver. O valor da área fica armazenado na posição da memória denominada “AREA”. Durante as décadas de 1960 e 1970 foram criadas a maioria das linguagens até hoje empregadas. Uma tarefa muito difícil é se fazer comparação entre linguagens de computação. Há inúmeros fatores que influenciam a escolha. Um fator muito importante é o acesso às próprias linguagens. Como a curva de aprendizado é muito lenta, o esforço investido implica uma certa inércia. Além disso, o esforço já realizado pode contar muito na escolha de uma linguagem de computação. Existem ainda membros da academia que se dedicam à linguagem FORTRAN de forma bastante ativa, pois existem muitas soluções prontas para problemas científicos, resultado de esforços de cientistas brilhantes que se debruçaram por décadas na solução de problemas. Embora haja alguns programas que fazem conversão de linguagens de programas, eles apresentam certas limitações e os códigos gerados ficam muitas vezes incompreensíveis. O resultado de um levantamento feito pelo site http://phylonetworks.blogspot.com.br/2013/12/results-­‐of-­‐some-­‐bioinformatics-­‐
polls.html sobre linguagens favoritas de bioinformatas está apresentado na figura 5. Esse levantamento pode ajudar na escolha de uma linguagem, embora haja também a possibilidade que se aprenda duas ou mais linguagens de programação. Figura 5. Levantamento das linguagens de programação favoritas por bioinformatas.