164 lines
3.9 KiB
Markdown
164 lines
3.9 KiB
Markdown
# Variable Environments
|
|
|
|
```haskell
|
|
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
|
|
|
|
```js
|
|
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
|
|
|
|
```haskell
|
|
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)
|
|
|
|
```
|
|
|
|
```shell
|
|
λ> 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
|
|
|
|
```haskell
|
|
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`
|
|
|
|
```haskell
|
|
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
|
|
|
|
```haskell
|
|
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
|
|
|
|
```haskell
|
|
data FileType = EXP | TAM
|
|
data Option = Trace | Run | Evaluate
|
|
|
|
main :: IO () --input output monad
|
|
```
|
|
|
|
This is the entry point; to compile:
|
|
|
|
```shell
|
|
$ ghc Main.hs -o aec
|
|
$ ./aec arith_example.exp --evaluate
|
|
Evaluating Expression: 45
|
|
```
|
|
|
|
```haskell
|
|
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
|
|
```
|