Trabalho Prático II
Programação Imperativa (PI2008)
José Carlos Ramalho
Alberto Simões
2008-05-26
Revisão: foram feitas várias correcções de modo a tornar o enunciado mais coincidente com o da disciplina de "Sistemas de Computação".
2008-04-05
Revisão: foi introduzida a definição da linguagem MSP.
2008-03-21
Revisão: foram introduzidas melhorias ao enunciada da primeira fase.
2008-03-06
Criada a primeira versão.
Palavras-chave: Programação Imperativa, Trabalho Prático, C
Este documento descreve o único tema disponível para a realização do trabalho prático que os alunos a fazer a disciplina em epígrafe têm de realizar de forma a obter uma avaliação prática à disciplina.
Ao longo de várias semanas, irá evoluindo e sofrendo alterações. Esteja atento às datas de revisões e aos comentários sobre as alterações introduzidas.
Índice
Capítulo 1
Capítulo 2
Capítulo 3
Secção 3.1
Secção 3.2
Capítulo 4
Capítulo 5
Capítulo 6
Secção 6.1
Subsecção 6.1.1
Subsecção 6.1.2
Subsubsecção 6.1.2.1
Subsubsecção 6.1.2.2
Subsubsecção 6.1.2.3



1. Objectivos de formação e resultados de aprendizagem

Este projecto tem como objectivos principais a formação genérica e específica de estudantes em fundamentos de computação na área da programação imperativa.
Os objectivos de formação genérica incluem: (i) a pesquisa, análise e selecção de informação, (ii) o treino na resolução de problemas, (iii) o desenvolvimento da capacidade de análise, e (iv) o desenvolvimento da capacidade de comunicação escrita e oral.
Os objectivos de formação específica incluem: (i) a análise da especificação e do problema, (ii) o desenvolvimento de algoritmos e consequente programação numa linguagem imperativa, (iii) a execução e realização de testes de conformidade.
A avaliação dos resultados esperados de aprendizagem irão verificar se as/os estudantes conseguem demonstrar ter adquirido o seguinte conjunto de competências genéricas e específicas:

2. Tema: "Mais Simples Possível (MSP)"

O tema escolhido para este projecto foi o da criação de uma máquina de
stack
virtual e do respectivo ambiente de edição e execução.
A máquina virtual será programada em
Assembly
numa linguagem muito simples definida para este contexto, o MSP.
O MSP é uma linguagem simples, com um número de instruções reduzido e com uma sintaxe e uma semântica bastante acessíveis. O MSP destina-se a programar uma Máquina de
Stack
Virtual. Como se verá mais à frente, é recorrendo a uma
stack
que a máquina efectua os seus cálculos. A designação de virtual surge do facto de que tal máquina não tem existência real, sendo, neste caso, da vossa responsabilidade a criação da ilusão de que ela existe.
Este trabalho será dividido em duas fases. Na primeira fase serás responsável pela criação da interface da máquina: edição de programas, carregamento, armazenamento e execução. Na segunda fase, terás de criar a máquina de stack e de executar nela os programas entretanto criados.
Os objectivos a atingir para a primeira fase aparecem descritos no capítulo 3. Enquanto que os objectivos a atingir na segunda fase, uma vez que são mais complexos, encontram-se descritos nos capítulos seguintes.
Resumindo, podemos enumerar na seguinte lista os objectivos a atingir na primeira fase:
  1. Especificação do modelo de dados para suportar o ambiente de edição, manipulação e execução de programas: programa (linhas de código), historial de comandos, ...
  2. Especificação e implementação das funcionalidades descritas no capítulo 3.
  3. Elaboração do respectivo relatório em LaTeX.
A seu tempo colocaremos aaqui os objectivos a atingir na segunda fase.

3. Ambiente de programação: "Vamos voltar aos anos 80"

O ambiente de programação que se pretende criar é muito semelhante ao que existia para as máquinas pessoais tipo
ZX Spectrum
nos anos 80.
Basicamente, um utilizador tem um monitor de caracteres à frente com uma área de trabalho útil de 25 linhas, em que cada linha tem 80 colunas. Por baixo dessas 25 linhas, existe uma linha especial que é a
prompt
de interacção. É nesta linha que o utilizador introduz os comandos do ambiente que levarão à criação e execução de programas.
Na figura 1 podemos ver o aspecto geral do ambiente.
Figura 1: Estado geral do ambiente de edição
No início, se o sistema fôr invocado sem nenhum programa:
$msp
O sistema deverá aparecer com o aspecto da figura 1.
No entanto, se o sistema fôr invocado com um programa:
$msp prog1.msp
O ambiente deverá apresentar as primeiras 25 linhas do programa (se este tiver mais de 25) e reflectir na linha de status a informação relativa ao programa que foi carregado (como se pode ver na figura 2).
Figura 2: Ambiente invocado com um programa: prog1.msp
Pode encarar este ambiente como um editor de texto parecido com o
vi
que acompanha normalmente o sistema operativo Linux.
O ambiente tem no topo uma linha de status para dar alguma informação ao utilizador: qual o ficheiro que está a ser editado, quantas linhas contem esse ficheiro,... Em baixo tem uma linha especial que será o ponto de entrada de comandos por parte do utilizador. Será nesta linha que o utiizador introduzirá comandos aos quais o ambiente deverá reagir.
Também à semelhança do
vi
o ambiente terá dois tipos de comandos:
Quando tiver tempo, poderá sofisticar a interface do sistema fazendo com que esta aceite abreviaturas dos comandos.
Estes dois tipos de comandos enumeram-se e descrevem-se nas subsecções seguintes.

3.1. Comandos de Operação

Nesta secção apresentam-se os comandos operacionais que o seu sistema deverá suportar. Tome as descrições seguintes como guias e não se deixe limitar por elas.
Use a imaginação...
O sistema deverá aceitar os seguintes comandos operacionais:
load <ficheiro>
Carregamento de programas: se o ficheiro existir na directoria corrente o ambiente deverá carregá-lo exibindo depois um écran semelhante ao mostrado na figura 2. O ambiente deverá reagir com uma mensagem de erro à inexistência do ficheiro na directoria corrente. No caso deste comando ser dado com um programa já a ser editado, o utilizador deverá ser consultado quanto ao armazenamento do programa que estava a ser editado antes do novo ser carregado.
save <ficheiro>
Armazenamento de programas: o ambiente deverá gravar o programa corrente no ficheiro designado. Se o nome do ficheiro fornecido diferir do ficheiro que estava a ser editado, o sistema deverá assumir este como o ficheiro actual para edição e deverá actualizar a linha de status.
history
Historial de comandos: à semelhança de um sistema Unix este comando permite listar todos os comandos introduzidos pelo utilizador até ao momento. Como resultado deste comando o écran deverá exibir os útimos 25 comandos dados pelo utilizador numerados de 1 a 25. Depois da listagem, a introdução de um
'\n'
na linha de comando fará regressar o sistema ao estado anterior.
com <n>
Execução de comandos anteriores: o
n
corresponde ao número de ordem de um comando anterior (dado pelo número de linha do editor); como resultado o sistema deverá voltar a executar esse comando.
hsave <ficheiro>
Armazenamento do historial num ficheiro: o ambiente deverá o historial no ficheiro designado (mais tarde poderá ser interessante olhar para a descrição da interacção ocorrida numa sessão).
clear
Reset do sistema: após este comando o sistema volta ao seu estado inical descartando tudo o que está a ser feito (programa que se está a editar e a memória de todos os comandos dados até ao momento; eventualmente, poderá ser pedido ao utilizador que confirme a execução deste comando.
run
Execução do programa que está no editor.
help
Lista os comandos disponíveis.
exit
Saída e abondono do sistema: todos os recursos alocados em tempo de execução deverão ser libertados.

3.2. Comandos de Edição

Estes comandos estão relacionados com a introdução/criação/alteração dos programas no sistema e têm uma estrutura diferente: começam todos por número de linha, a seguir têm o nome do comando seguido de opções caso as haja.
<int> go
Posicionamento da janela de visualização: após este comando a primeira linha da janela deverá corresponder à linha com número:
<int>
.
<int> insert <comando msp>
Inserção de uma linha nova: a nova linha deverá ser inserida imediatamente antes da linha com número
<int>
e o seu conteúdo será
<comando msp>
.
<int> append <comando msp>
Acrescento de uma linha: a nova linha deverá ser acrescentada imediatamente a seguir à linha com número
<int>
e o seu conteúdo será
<comando msp>
.
<int> delete
Apagar uma linha: a linha com número <int> deverá ser apagada.
<int> replace <comando msp>
Substituir uma linha: a linha com número <int> é substituída pelo novo <comando msp> introduzido pelo utilizador.

4. Máquina Virtual de Stack

Numa Máquina de
Stack
, podem-se identificar os seguintes blocos:
Memória
Área lógica para armazenamento de instruções e valores. Divide-se em 3 blocos independentes com funcionalidades distintas:
  • Memória de Programa (ou abreviadamnte MProg);
  • Memória de Dados (ou MDados);
  • Memória de Trabalho (Stack).
Descodificador
Unidade encarregue de interpretar e mandar executar cada instrução;
Unidade Lógica e Aritmética
Unidade que tem a responsabilidade de efectuar as operações lógicas e aritméticas (na nossa máquina será materializada num conjunto de funções que efectuarão as operações referidas);
Input e Output
São duas posições de memória especiais, com endereços fixos e bem conhecidos:
input
e
output
; Têm a característica especial de estarem ligadas ao exterior, permitindo a entrada de valores para a máquina (
input
) e a saída de valores da máquina (
output
); em concreto, estas células de memória estão ligadas ao teclado (
input
) e ao monitor (
output
).
Bus Interno
É o "corredor" lógico qu liga as várias unidades permitindo a circulação e comunicação de instruções e valores (na nossa máquina implementada em C não terá uma materialização concreta).
Instruction Pointer (IP) e Stack Pointer (SP)
São os únicos registos da nossa máquina. O IP contem sempre, num dado instante, o endereço da próxima instrução que deve ser executada (endereço de MProg). O SP contem o endereço da última posição ocupada na
Stack
(ou seja, a posição do valor no
topo
da
Stack
).
Figura 3: Arquitectura da Máquina de Stack
A figura 3 apresenta a arquitectura da Máquina de Stack de acordo com os blocos funcionais descritos anteriormente.
Cada célula de memória (
MProg
,
MDados
ou
Stack
) tem capacidade para armazenar 2
bytes
(sequência de 16
bits
) e está associada a um enedereço que a identifica univocamente.
Um endereço é um número inteiro que tem o valor 0 para a primeira posição de memória e sofre incrementos de 1 para as posições seguintes até à última célula. Nesta máquina virtual definiu-se o valor 65536 como o número total de células de memória. Portanto, a gama de endereços possíveis na nossa máquina virtual é dada pelo seguinte intervalo: [0, 65535].
O valor que é armazenado em determinada célula de memória pode representar uma instrução, um argumento de uma instrução, um valor inteiro (como veremos mais à frente num dos intervalos: [0, 65536]  ou [-32767, +32767]), um carácter ou um componente de um endereço.
A interpretação do significado de cada valor é da responsabilidade da máquina e baseia-se no tipo de memória à qual se está a aceder em determinado instante:
Memória de Programa (MProg)
Armazena as instruções que vão ser executadas pela máquina. Um
programa
é uma
sequência de instruções
armazenadas na MProg. Uma célula da MProg pode conter o código de uma instrução ou o argumento de uma instrução. A maioria das instruções da linguagem MSP não contem argumentos. Os argumentos, se existirem, localizam-se nas posições seguintes à do código da instrução.
Memória de Dados (MDados)
Armazena valores. Esses valores correspondem aos dados do problema ou aos resultados calculados pelo programa. Cada valor ocupa dois
bytes
, podendo representar grandezas numéricas no intervalo [-32768,32767], ou caracteres (pelo seu código ASCII respectivo), ou ainda endereços de células da MDados.
Stack
Memória de trabalho semelhante no conteúdo à MDados. Contudo, é acedida e usada segundo uma filosofia LIFO ("Last In First Out"): os valores que se vão introduzindo na
Stack
ficam empilhados uns por cima dos outros, de tal forma que apenas se pode aceder (ler, consultar) o valor que está no cimo (topo) da
Stack
, e que corresponde ao último valor que lá foi armazenado. Assim, apenas é necessário conhecer um único endereço: o da última posição, ou topo da
Stack
. Considera-se que o topo é o endereço da
Stack
relativo ao último valor armazenado. O próximo valor a guardar na
Stack
será armazenado no endereço a seguir ao topo, e o primeiro valor a sair será sempre o do topo. A Máquina de
Stack
foi desenhada de tal forma que todas as operações esperam ter os seus operandos armazenados em posições consecutivas a partir do topo, retiram-nos de lá e, em sua substituição, coloca-se no topo o resultado da sua computação. Na Máquina de
Stack
, o topo "cresce do fim para o princípio", ou seja, do último endereço disponível (65535) em direcção ao primeiro (0).

5. Funcionamento

Para um programa ser executado o IP é carregado com o endereço de MProg onde está a primeira instrução a ser executada (como no nosso caso estamos a interpretar linha a linha o programa, bas ta a indicação do número de linha onde está a primeira instrução).
A partir daqui o funcionamento é sistemático: descodifica-se a instrução, dão-se as ordens necessárias para a executar, e coloca-se no IP a indicação da próxima instrução a executar (atenção que na maior parte dos casos esta será a instrução seguinte mas no caso de haver saltos poderá ser outra qualquer).
Este processo continua até que seja executada a instrução que manda parar a execução do programa.
Como exemplo de acções a realizar para executar uma dada instrução podemos apresentar entre outras as seguintes:

6. Linguagem MSP

Relativamente à linguagem MSP, e quando se estiver a analisar a linguagem, convem estar atento aos seguintes pormenores:

6.1. Sintaxe e Semântica

6.1.1. Zona de Dados: declaração de variáveis

A Zona de Dados é iniciada pelas palavras reservadas
MEMORIA de DADOS
e prolonga-se até ao início da Zona de Código, iniciada pela palavra reservada
CODIGO
.
É na Zona de Dados que se declaram e podem inicializar as variáveis que irão ser utilizadas pelo programa.
A declaração de uma variável tem a seguinte forma:
identificador-variável endereço TAM tamanho VAL valor1 valor2 ... valorn
Por exemplo:
x 100 TAM 20 VAL 4
Declara uma variável com identificador "
x
", no endereço 100, com tamanho 20 e com o primeiro
valor
inicializado com 4 (os
valores
nos endereços 101 ao 119 são inicializados por omissão com o valor 0).
A smântica das declarações compreende as seguintes características:

6.1.2. Zona de Código: instruções

A Zona de Código inicia-se pela palavra reservada
CODIGO
e prolonga-se até ao fim do texto.
O conjunto das instruções pode-se dividir em três grupos de acordo com as repectivas funcionalidades: instruções para manipulação de valores e endereços, instruções aritméticas e lógicas e instruções de controlo da sequência de execução do progrma.

6.1.2.1. Manipulação de Valores e Endereços

PUSH [valor]
Coloca
valor
no topo da Stack;
PSHA [endereço ou identificador de variável]
Coloca o endereço fornecido ou o endereço da variável correspondente ao identificador fornecido no topo da Stack;
LOAD
Retira da Stack um endereço e vai buscar a essa posição de memória o valor lá armazenado que coloca no topo da Stack;
LDA
Retira da Stack um endereço e vai buscar a essa posição de memória um endereço que coloca no topo da Stack;
STORE
Retira da Stack primeiro um valor, depois um endereço e coloca na posição da Memória de Dados referente ao endereço o valor retirado inicialmente da Stack;
STRA
Retira da Stack primeiro um endereço, depois outro endereço e coloca na posição da Memória de Dados referente ao segundo endereço o primeiro endereço retirado da Stack;
IN
Coloca no topo da Stack o conteúdo da posição especial
input
resultante da leitura de um valor via teclado;
OUT
Escreve no monitor o valor que é retirado do topo da Stack;
INC
Coloca na Stack o conteúdo (código ASCII) da posição especial
input
, resultante da leitura de um carácter via teclado;
OUTC
Escreve no monitor o carácter cujo código ASCII é retirado da Stack;
Observações: as instruções
PUSH, LOAD
e
STORE
operam sobre valores inteiros enquanto que
PSHA, LDA
e
STRA
operam sobre endereços.

6.1.2.2. Instruções Aritméticas e Lógicas

ADD
Retira dois inteiros da Stack, soma-os e coloca na Stack o resultado;
SUB
Retira dois inteiros da Stack, subtrai o segundo ao primeiro e coloca na Stack o resultado;
MUL
Retira dois inteiros da Stack, multiplica-os-os e coloca na Stack o resultado;
DIV
Retira dois inteiros da Stack, divide o primeiro pelo segundo e coloca na Stack o resultado;
ADDA
Retira um inteiro e um endereço da Stack; soma o inteiro ao endereço calculando um novo endereço que é por fim colocado na Stack;
AND
Retira dois inteiros da Stack, calcula a sua conjunção lógica e coloca na Stack o resultado;
OR
Retira dois inteiros da Stack, calcula a sua disjunção lógica e coloca na Stack o resultado;
NOT
Retira um inteiro da Stack, calcula a sua negação lógica e coloca na Stack o resultado;
EQ
Retira dois inteiros da Stack, verifica se são iguais e coloca na Stack o resultado da comparação;
NE
Retira dois inteiros da Stack, verifica se são diferentes e coloca na Stack o resultado da comparação;
LT
Retira dois inteiros da Stack, verifica se o primeiro é menor que o segundo e coloca na Stack o resultado dessa comparação;
LE
Retira dois inteiros da Stack, verifica se o primeiro é menor ou igual que o segundo e coloca na Stack o resultado dessa comparação;
GT
Retira dois inteiros da Stack, verifica se o primeiro é maior que o segundo e coloca na Stack o resultado dessa comparação;
GE
Retira dois inteiros da Stack, verifica se o primeiro é maior ou igual que o segundo e coloca na Stack o resultado dessa comparação;
ANDB
Retira dois inteiros da Stack, calcula a sua conjunção
bit-a-bit
e coloca na Stack o resultado;
ORB
Retira dois inteiros da Stack, calcula a sua disjunção
bit-a-bit
e coloca na Stack o resultado;
NOTB
Retira um inteiro da Stack, calcula a sua negação
bit-a-bit
e coloca na Stack o resultado;
Observações:

6.1.2.3. Instruções de Controlo

JMP [id-label ou endereço ou endereço-relativo]
Salta incondicionalmente para o endereço calculado a partir do argumento (i.e., coloca em IP esse endereço); a execução do programa continua com o código armazenado no endereço da MProg especificado por
id-label
, ou no endereço (em valor absoluto relativo ao início da MProg) ou somando ao IP o endereço-relativo passado como argumento; neste último caso, o valor do argumento deverá obrigatoriamente conter o sinal + ou - antes do valor numérico
JMPV [id-label ou endereço ou endereço-relativo]
Retira o valor no topo da stack e testa-o (assumindo que lá está um valor Booleano): se for Verdadeiro salta para o endereço calculado a partir do argumento; se for Falso a execução continua na instrução apontada pelo valor do IP;
CALL [id-label ou endereço ou endereço-relativo]
Guarda na Stack o endereço da instrução que se lhe segue e prossegue executando a instrução que se encontra no endereço passado como argumento (Chamada incondicional de uma subrotina);
RET
Efectua o retorno de uma subrotina: a execução do programa continua na instrução que está no endereço que é retirado do topo da Stack;
HALT
Pára a execução do programa;
NOOP
Não faz nada, serve apenas para gastar tempo...
Observações: