4.3 KiB
Compiling Variables
A variable is identified by an alphanumeric string. We can store this as a list of pairs, with the variable's identifier and its value.
Variable Environment or VarEnv - [(Identifier, Stack Address)]
A stack address is an integer value that specifies where in the stack that variable is contained. The bottom of the stack is reserved for variable values.
The bottom of the stack is indexed 0.
Let's say our environment consists of 3 variables named x, y, z. It would look like:
[("z",2), ("y",1), ("x",0)]
| Variables | Stack (Values) | Index |
|---|---|---|
| x | 7 | 0 |
| y | 2 | 1 |
| z | 9 | 2 |
To get the value of a variable from the stack, TAM uses the instruction LOADL a where a is a stack address. LOADL will get the value and copy the value to the top of the stack.
LOAD a - copy address a to top of stack
STORE a - pop top of stack to address a
For example, if LOADL 2 is called, it will affect the stack in the following way:
| Variables | Stack (Values) | Index |
|---|---|---|
| x | 7 | 0 |
| y | 2 | 1 |
| z | 9 | 2 |
| … | ||
| 9 |
expCode :: VarEnv -> Expr -> [TAMInst]
Before, we just called the abstract syntax tree AST; however, with the extended grammar, we will now have multiple ASTs: one for programs, one for commands and one for expressions. The AST for expressions we call Expr.
Remember in our compiler, the stack is represented and stored as a list, with the top of the stack being the head of the list.
Declaration of Variables
let var x; //no value given means initialised to 0
var y := 5 //note no semicolon
var z;
in ...
For the code above, we need to generate a VarEnv. The compiler needs to generate a variable environment and TAM code.
VarEnv: [("z",2), ("y",1), ("x",0)]
TAM code stack: [0,5,0]
However we also need to account for expressions such as:
let var x := 3;
var y := 5;
var z := x*y
declarationCompiler :: [Declaration] -> (VarEnv, [TAMInstr])
VarEnv :: [(Identifier, Address)]
NOTE: this can be defined with functions given in the FunParser library. Or using a state monad
State Monad
s_0 \rightarrow s_1 \rightarrow s_2 \rightarrow s_n for each change in state, there's a corresponding result generated.
a_0 \quad\space\space\space a_1 \quad\space\space\space a_n
-
For each of these states, we need a variable environment and address
-
For each of the results, we need to generate TAM instructions.
Example: s_n could be your bank balance and a_n could be the purchase history.
- In our case:
- States are VarEnv & next free address space for next variable
- Outputs are TAM instructions
We need to define a type that models a state transform, while at the same time producing a result. This is where a state monad comes in.
newtype ST st a = S (\st -> (a, st))
-- ST - state transformer
-- st - type of states
-- a - type of output/results
-- S - constructor
-- \st a function that takes a state and returns a value along with a new state
-- this is a general type definition with state type st and result type a
-- this is still just a type constructor, has to be applied to a type
instance Functor (ST st)
instance Applicative (ST st)
instance Monad (ST st)
--as we inherit the monad class, we can use do notation
newtype ST st a = S (\st -> (a, st))
--type definition
ST Int
--type constructor
ST Int String
--type
app :: ST st a -> st -> (a, st)
app (S f) x = f x
--applies the constructor to state x
instance Functor (ST st) where
--fmap :: (a->b) -> ST st a -> ST st b
fmap g sta = S (\s -> let (x,s') = app sta s
in (g x, s'))
instance Applicative (ST st) where
--pure :: a -> ST st a
pure x = S (\s -> (x,s))
--(<*>) :: (ST st (a -> b)) -> ST st a -> ST st b
stf <*> sta = S (\s -> let (f,s') = app stf s
(x,s'') = app sta s')
in (f x, s''))
instance Monad (ST st) where
return = pure
-- (>>=) :: (ST st a) -> (a -> ST st b) -> ST st b
sta >>= f = S (\s -> let (x,s') = app sta s
(y,s'') = app (f x) s'
in (y,s''))