notes/docs/lectures/compilers/09_variable_enviroments.md

Variable Environments

type VarEnv = [(Identifier, StkAddress)]
--				String		Int

address :: VarEnv -> Identifer -> StkAddress
address ve v = case lookup v ve of
				Nothing -> error "variable not in enviroment"
				Just a -> a
--Expr is AST of expressions
expCode :: VarEnv -> Expr -> [TAMInstr]
expCode ve (LitInteger x) = [LOADL x]
-- we must put variable value on top of the stack
expCode ve (Var v) = [LOAD (address ve v)]

How do we build a variable environment?

Every program begins with a sequence of variable declarations

var x := 7;
var y := 3;
var z;
var w := x * y - 2

The parser will turn this into a list of ASTs for declarations

Then we have to use this to build a variable environment, and generate TAM code to write the values of the variables onto the stack.

We do this using the state monad

• We use as an underlying state the variable environment itself, as we build it sequentially
• We also keep the stack address as a state, where it keeps the next free address

declsCode :: [Declarations] -> (VarEnv, [TAMInstr])
declsCode ds = let (tam,(ve,0a)) app (declsTAM ds) ([],0) --initial state
				in (ve,tam)
				
declsTAM :: [Declarations] -> ST (VarEnv, StkAddress) [TAMInstr]
declsTAM [] = return []
declsTAM (d:ds) = do
				td <- declTAM d
				tds <- declsTAM ds
				return (td++tds)

declTAM :: Declarations -> ST (VarEnv, StkAddress) [TAMInstr]
declTAM (VarDecl v)   = do
						(ve,a) <- stState
						stUpdate ((v,a) : ve, a+1)
                        return [LOADL 0]
declTAM (VarInit v e) = do
						(ve,a) <- stState
						stUpdate ((v,a) : ve, a+1)
                        return (expCode ve e)

λ> parseAll declarations "var x:=7;var y:=3;var z;var w:=x*y-2"
[VarInit "x" (LitInteger 7), VarInit "y" (LitInteger 3), VarDecl "z", VarInit "w" (BinOp Subtraction (BinOp Multiplication (Var "x") (Var "y")) (LitInteger 2))]

λ> ds = parseAll declarations "var x:=7;var y:=3;var z;var w:=x*y-2"

λ> (ve,tam) = declsCode ds
λ> ve
[("w",3),("z",2),("y",1),("x",0)]
λ> tam
[LOADL 7, LOADL 3m LOADL 0, LOAD 0, LOAD 1, MUL, LOADL 2, SUB]
λ> execTAM [] tam
[19, 0, 3, 7]

Designing ASTs for any grammar

• We turn every non-terminal of the grammar into a type of AST

• We turn every production of the non-terminal into a constructor of the type

Defining the grammar of TAM

command ::= identifier := expr
			| if expr then command else command
			| while expr do command
			| getint ( identifier )
			| printint ( expr )
			| begin commands end

Here: :=, if, then, else, while, do, getint, printint, begin, end, (, ) are terminals

data Command = 

datatypes Identifier = String, Expr, Commands -- [Command]

Assign to every production one constructor for the data type.

This means we will have 6 constructors called Assignment, IfThenElse, WhileDo, GetInt, PrintInt, BeginEnd

data Command = Assignment Identifier Expr
				| IfThenElse Expr Command Command
				| WhileDo Expr Command
				| GetInt Identifer
				| PrintInt Expr
				| BeginEnd [Command]
				
type Commands = [Command]
--or 
data Commands = SingleC Command
				| MultipleC Command Commands

Organising a Haskell Project

There are 6 Haskell modules, Main.hs is the entry point.

Defining a Module

module <filename> where
import ...
--definitions
newtype ...
--functions
func :: a -> b

Note file name must start with a capital

When you import a module, you can use functions defined in the module

data FileType = EXP | TAM
data Option = Trace | Run | Evaluate

main :: IO () --input output monad

This is the entry point; to compile:

$ ghc Main.hs -o aec
$ ./aec arith_example.exp --evaluate
Evaluating Expression: 45

stUpdate :: st -> ST st ()
stUpdate s = S (\_ -> ((), s))

stGet :: ST st st
stGet = S (\s -> (s,s))

stRevise :: (st -> st) -> ST st ()
stRevise f = stGet >>= stUpdate . f