{- 
  Expressões aritméticas: sintaxe e semântica 
  Pedro Vasconcelos, 2009, 2010
-}
module Expr where

-- sintaxe abstracta de expressões
data Expr = Num Int
          | Add Expr Expr
          | Mult Expr Expr
            deriving (Eq, Show)

-- interpretador operacional
eval :: Expr -> Int
eval (Num n) = n
eval (Add e1 e2) = eval e1 + eval e2
eval (Mult e1 e2) = eval e1 * eval e2


-- instruções para uma máquina de pilha
data Instr = PUSH Int
           | ADD
           | MUL
             deriving (Eq,Show)

-- código (lista de instruções)
type Code = [Instr]

-- compilador
-- dada uma expressão, produz a sequência de instruções
compile :: Expr -> Code
compile (Num n) = [PUSH n]
compile (Add e1 e2) = compile e1 ++ compile e2 ++ [ADD]
compile (Mult e1 e2) = compile e1 ++ compile e2 ++ [MUL]


-- pilha: lista de valores (inteiros)
type Stack = [Int]

-- estado da máquina: par de pilha, código
type State = (Stack, Code)

-- transição de estado: implementa uma instrução
exec :: State -> State
exec (stack, PUSH n:code)    = (n:stack, code)
exec (v1:v2:stack, ADD:code) = (v1+v2:stack, code)
exec (v1:v2:stack, MUL:code) = (v1*v2:stack, code)
exec (stack, [])             = error "fim do programa"



-- executar um programa (partindo da pilha vazia)
run :: Code -> Int
run code = runInstr ([],code)

-- executar todas as instruções
-- o resultado é o topo da pilha
runInstr :: State -> Int
runInstr (v:_,[])  = v
runInstr s         = runInstr (exec s)



{- --------------------------------------------------------
   Alguns exercícios propostos:
   ---------------------------------------------------------

1) Definir uma função 

                 repr :: Expr -> String

   que converte uma expressão numa representação em
   sintaxe concreta. Sugestão: pode acrescentar 
   parêntesis a mais....

2) Acrescente operadores para subtracção e divisão (inteira)
   à linguagem e modifique o interpretador e compilador
   para esses novos casos.

3) Duas expressões equivalentes podem resultar em execuções
   muito diferentes. Por exemplo: podemos calcular a soma 
   de inteiros de 1 a n usando 
               1+(2+(3+(... + n)))
   ou 
               ((((1+2)+3)+ ...)+n).
   Investigue qual das duas formas necessita de menor tamanho 
   máximo de pilha.

4) Modifique o interpretador da máquina virtual de forma
   a calcular além do resultado também qual o máximo
   comprimento da pilha necessário durante a execução de
   um programa.

-}