Enunciado do Projecto0708

Considere o seguinte tipo Haskell para representar uma linguagem de programação imperativa muito simples:

data Exp = Const Int 
         | Var String 
         | Add Exp Exp 
         | Sub Exp Exp

data Cond = Eq Exp Exp 
          | Gt Exp Exp

data Lang = Atrib String Exp 
          | If Cond Lang Lang 
          | While Cond Lang 
          | Seq Lang Lang

Na linguagem Lang seria possível escrever um programa para calcular o máximo de dois números da seguinte forma:

x = 3;
y = 4;
if (x>y) r = x else r = y;

Note que nesta linguagem não existe input/output, sendo o resultado de executar um programa o valor final das suas variáveis. As variáveis de um programa Lang são sempre do tipo inteiro. Em Haskell este programa seria representado pelo seguinte termo:

maximo :: Lang
maximo = Seq (Atrib "x" (Const 4)) $ 
         Seq (Atrib "y" (Const 3)) $ 
         If (Gt (Var "x") (Var "y")) (Atrib "r" (Var "x")) 
                                     (Atrib "r" (Var "y"))

Usando ciclos é possível escrever programas um pouco mais sofisticados, como por exemplo o seguinte que coloca em r o resultado de multiplicar x e y.

x = 4;
y = 3;
r = 0;
while (y>0) {r = r + x; y = y - 1}

Tarefa 1
Escrever um interpretador para a linguagem Lang, ou seja, uma função que dado um programa devolve o valor final das suas variáveis.

Relembre a arquitectura Y86 que é leccionada nas disciplinas de Sistemas de Computação e Arquitectura de Computadores. A descrição simplificada desta arquitectura pode ser encontrada aqui.

É relativamente simples compilar programas escritos em Lang para esta arquitectura. Por exemplo, o seguinte programa em Y86 é um possível resultado de compilar o programa maximo.

  .pos 0
  irmovl stack, %esp
  jmp main
x:
  .long 0
y:
  .long 0
r:
  .long 0
main:
  irmovl 4, %eax
  irmovl x, %ecx
  rmmovl %eax, 0(%ecx)
  irmovl 3, %eax
  irmovl y, %ecx
  rmmovl %eax, 0(%ecx)
  irmovl x, %ecx
  mrmovl 0(%ecx), %ebx
  irmovl y, %ecx
  mrmovl 0(%ecx), %eax
  subl %eax, %ebx
  jle else
  irmovl x, %ecx
  mrmovl 0(%ecx), %eax
  irmovl r, %ecx
  rmmovl %eax, 0(%ecx)
  jmp fim
else:
  irmovl y, %ecx
  mrmovl 0(%ecx), %eax
  irmovl r, %ecx
  rmmovl %eax, 0(%ecx)
fim:
  halt
  .pos 0x100
stack:

Tarefa 2
Escrever um compilador que, dado um programa escrito em Lang, gere um programa Y86 equivalente.

Para que o programa acima possa executar na máquina Y86 tem que antes passar por um assembler, que o converte numa sequência de bytes pronta a carregar na memória. Cada instrução é codificada numa sequência de 1 a 6 bytes de acordo com o documento acima referido. Também é necessário converter a tags em endereços de memória absolutos, tendo em atenção não só o comprimento de cada instrução, mas também as directivas pos usadas.

Tarefa 3
Escreva um assembler que, dado um programa escrito em Y86, gere a sequência de bytes que o implementa.

Depois de passado pelo assembler, um programa está finalmente pronto a executar.

Tarefa 4
Implemente um simulador da arquitectura Y86. Este simulador é uma função que, dada a sequência de bytes produzida pelo assembler, carrega essa sequência na memória e começa a execução do programa com o PC a zero. O resultado desta função é o estado final da memória, dos registos e das flags.

Tarefa 5

Para além das tarefas apresentadas acima, cada grupo deve implementar mais alguma funcionalidade à sua escolha. Sugerem-se as seguintes, por ordem de preferência: teste da correcção do compilador usando QuickCheck; incluir funcionalidades de debugging no simulador que permitam consultar o estado da máquina durante a sua execução; extender a funcionalidade da linguagem Lang, nomeadamente incluindo a possibilidade de definir e invocar funções.

Logística

O projecto deverá ser realizado em grupos de 3 alunos. Toda a documentação (vulgo relatório) deve ser desenvolvida em literate Haskell ou afins (Haddock, lhs2TeX, ...).

Para ter aprovação no projecto é necessário executar no mínimo a tarefa 4 mais uma das 3 primeiras tarefas. A tarefa 5 vale 3 valores. Naturalmente, deverão sempre que possível usar monads na resolução das tarefas descritas.

O projecto deverá ser apresentado preferencialmente nos dias 12 e 13 de Maio à tarde. Opcionalmente, poderá ser apresentado no dia 7 de Maio também à tarde. A apresentação terá a duração de 30m. As folhas para marcação da apresentação serão disponibilizadas na recepção do departamento na semana de 7 a 11 de Abril. Não serão permitidas marcações fora deste período.