963117a7efcf202fe2d03e045dd49b11fa1a6eec
[barrelfish] / tools / fof / IL / Paka / Builders.lhs
1 %if false  
2   Copyright (c) 2009, ETH Zurich.
3   All rights reserved.
4   
5   This file is distributed under the terms in the attached LICENSE file.
6   If you do not find this file, copies can be found by writing to:
7   ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
8 %endif
9
10 %include polycode.fmt
11
12 %if false
13
14 > module IL.Paka.Builders where
15
16 > import Text.PrettyPrint.HughesPJ
17 > import qualified Data.Map as Map
18 > import Debug.Trace
19
20 > import PureExpressions
21
22 > import IL.Paka.Syntax
23
24 %endif
25
26 \section{Paka building blocks}
27
28 I'm particularly proud of the Paka code generation architecture. To
29 build a Paka term, we simply call some builders functions which are
30 chained up together with the |#| operator. These builders take care of
31 inserting the definitions in the right place in |PakaCode|,
32 |PakaIntra|, or sequentially extend the |ILPaka| code. Thanks to that
33 machinery, we don't have to explicitly build these data-structures, we
34 just call functions.
35
36 Hence, a builder is just putting a brick in the |PakaBuilding| wall:
37
38 > type PakaBuilding = (ILPaka -> ILPaka, PakaCode, PakaIntra)
39
40 That is, operations taking some arguments and extending a
41 |PakaBuilding| into a new one.
42
43
44 \subsection{Low-level machinery}
45
46 To give a feeling of ``sequential code'', the |#| operator is simply
47 an inversed composition operation:
48
49 > f # g = \x -> g (f x) 
50
51 Using |#|, we will compose our builders with a sequential feeling.
52
53 Because most, if not all, operations modify one element of the
54 |PakaBuilding| triple, we define the following combinators:
55
56 > first :: (a -> b) -> (a, c, d) -> (b, c, d)
57 > first f (a,b,c) = (f a, b, c)
58 >
59 > second :: (a -> b) -> (c, a, d) -> (c, b, d)
60 > second f (a,b,c) = (a, f b, c)
61 >
62 > third :: (a -> b) -> (c, d, a) -> (c, d, b)
63 > third f (a,b,c) = (a,b,f c)
64
65
66 \subsection{Building |PakaCode|}
67
68 We can add new C includes:
69
70 > include :: String -> PakaBuilding -> PakaBuilding
71 > include id = second $ include' id 
72 >     where include' id globalEnv 
73 >               = case id `Map.lookup` incls of
74 >                   Nothing -> globalEnv { includes = Map.insert id decl incls }
75 >                   Just _ -> globalEnv
76 >               where incls = includes globalEnv
77 >                     decl = text "#include" <+> text id 
78
79 We can declare new C types:
80
81 > declare :: String -> Doc -> Doc -> PakaBuilding -> PakaBuilding
82 > declare id typ decl = second $ declare' id typ decl
83 >     where declare' id typ decl globalEnv =
84 >               case id `Map.lookup` typs of
85 >                 Nothing -> globalEnv { declarations = (id,decl) : decls,
86 >                                        types = Map.insert id typ typs }
87 >                 Just _ -> globalEnv
88 >               where decls = declarations globalEnv
89 >                     typs = types globalEnv
90
91 We can declare global variables:
92
93 > globalVar :: String -> Doc -> PakaBuilding -> PakaBuilding
94 > globalVar id def = second $ globalVar' id def
95 >     where globalVar' id def globalEnv =
96 >               case id `lookup` vars of
97 >                 Nothing -> globalEnv { globalVars = (id,def) : vars  }
98 >                 Just _ -> globalEnv
99 >               where vars = globalVars globalEnv
100
101 We can add function prototypes:
102
103 > prototype :: String -> Doc -> PakaBuilding -> PakaBuilding
104 > prototype id proto = second $ prototype' id proto
105 >     where prototype' id proto globalEnv =
106 >               case id `Map.lookup` protos of
107 >                 Nothing -> globalEnv { prototypes = Map.insert id proto protos }
108 >                 Just _ -> globalEnv
109 >               where protos = prototypes globalEnv
110
111 And we can define new functions:
112
113 > function :: Doc -> Doc -> String -> Doc -> PakaIntra -> ILPaka -> PakaBuilding -> PakaBuilding
114 > function returnT attrs funName funArgs lEnv body = 
115 >     second $ function' returnT attrs funName funArgs lEnv body
116 >     where function' returnT attrs funName funArgs lEnv body gEnv =
117 >               case funName `Map.lookup` functions' of
118 >                 Nothing -> gEnv { functions = Map.insert funName (returnT, attrs, funName, funArgs, lEnv, body) functions' }
119 >                 Just _ -> gEnv
120 >               where functions' = functions gEnv
121
122
123 \subsection{Building |PakaIntra|}
124
125 As for global variables in the |PakaCode|, we can add local variables
126 in the |PakaIntra| environment:
127
128 > localVar :: String -> Doc -> PakaBuilding -> PakaBuilding
129 > localVar id def = third $ localVar' id def
130 >     where localVar' id def localEnv 
131 >               = case id `Map.lookup` vars of
132 >                   Nothing -> localEnv { localVars = Map.insert id def vars  }
133 >                   Just _ -> localEnv
134 >               where vars = localVars localEnv
135
136 And we can bring a constant in the |PakaIntra|:
137
138 > constant :: PureExpr -> PakaBuilding -> PakaBuilding
139 > constant e = third $ constant' e
140 >     where constant' e lEnv = lEnv { expr = Just e }
141
142 \subsection{Building |ILPaka|}
143
144 Obviously, the serious stuff happens in |ILPaka|, or more precisely
145 |ILPaka -> ILPaka|: this code is seriously continuation-passing. The
146 plan is that we want to build a |ILPaka| value. However, we note that,
147 for instance, to build a |PStatement| value, we need to know the
148 remaining code. But we don't know it yet, as we are compiling it! So,
149 we return a continuation that waits for that uncompiled chunk and plug
150 it in the right place. Continuation-passing style, yay!
151
152 As an example of that technique in action, take a look at |instr| and
153 |assgn| below. Apart from that CPS detail, they are computationally
154 trivial, bringing their arguments in the right place of the
155 constructor and returning by calling the continuation.
156
157 > instr :: Term -> [PakaVarName] -> PakaBuilding -> PakaBuilding
158 > instr instruction vars = first $ instr' instruction vars
159 >     where instr' instruction varNames k 
160 >               = \c ->
161 >                 k $ PStatement (PInstruction instruction varNames) c
162 >
163 > assgn :: PakaVarName -> Term -> [PakaVarName] -> PakaBuilding -> PakaBuilding
164 > assgn wVarName assgnmt rVarNames = first $ assgn' wVarName assgnmt rVarNames
165 >     where assgn' wVarName assgnmt rVarNames k
166 >               = \c ->
167 >                 k $ PStatement (PAssign wVarName assgnmt rVarNames) c
168
169 As you can expect, we need to stop ``continuating'' at some
170 point. This naturally fits with the role of closing terms:
171
172 > close :: PakaClosing -> PakaBuilding -> PakaBuilding
173 > close c = first $ close' c
174 >     where close' c = \k _ -> k (PClosing c)
175
176 Similarly, the control-flow operators closes all their branches and
177 only continue downward:
178
179 > pif :: ILPaka -> PureExpr -> ILPaka -> ILPaka -> PakaBuilding -> PakaBuilding
180 > pif cond test ifTrue ifFalse = first $ pif' cond test ifTrue ifFalse
181 >     where pif' cond test ifTrue ifFalse cont = \c ->
182 >               cont $ PIf cond test ifTrue ifFalse c
183 >
184 > pwhile :: ILPaka -> PureExpr -> ILPaka -> PakaBuilding -> PakaBuilding
185 > pwhile cond test loop = first $ pwhile' cond test loop
186 >     where pwhile' cond test loop cont = \c ->
187 >               cont $ PWhile cond test loop c
188 >
189 > pdoWhile :: ILPaka -> ILPaka -> PureExpr -> PakaBuilding -> PakaBuilding
190 > pdoWhile loop cond test = first $ pdoWhile' loop cond test
191 >     where pdoWhile' loop cond test cont = \c ->
192 >               cont $ PDoWhile loop cond test c
193 >
194 > pswitch :: PureExpr -> [(PureExpr,ILPaka)] -> ILPaka -> PakaBuilding -> PakaBuilding
195 > pswitch test cases defaultCase = first $ pswitch' test cases defaultCase
196 >     where pswitch' test cases defaultCase cont = \c ->
197 >               cont $ PSwitch test cases defaultCase c
198