Initial commit: 0.4.3.0 from hackage
[harpy.git] / doc / larger-tutorial.lhs
1 \documentclass[a4paper,11pt]{article}
2
3 \usepackage[margin=2.5cm]{geometry}
4 \usepackage{hyperref}
5
6 %include polycode.fmt
7 %format alpha = "\alpha"
8
9
10 \title{\textbf{Slightly Larger Harpy Tutorial}}
11 \author{Martin Grabm├╝ller \and Dirk Kleeblatt}
12
13 \begin{document}
14 \maketitle
15 \begin{abstract}\noindent
16 This tutorial is an introduction to some of the more advanced features
17 of Harpy.  In the course of the tutorial, we will build a small
18 run-time compiler for a call-by-value lambda-calculus.
19 This document is written as a literate Haskell program, so you can
20 compile and run it without any modifications.  
21 \end{abstract}
22
23 \section{Introduction}
24
25 In this tutorial, we develop a small run-time compiler for a simple
26 call-by-value lambda calculus extended with natural number constants.
27
28 Before reading, you should have read the Harpy tutorial, which
29 introduces the most basic concepts.  We also recommend to have a
30 running \verb|ghci| session running for loading the literate Haskell
31 script of this tutorial and to try it out.  Maybe you want to have the
32 Harpy API documentation available, too.
33
34 \section{The Code}
35
36 To make use of Harpy and (a subset of) the x86 assembler instructions, we need
37 to import some modules.
38
39 \begin{code}
40 import Harpy.CodeGenMonad
41 import Harpy.X86Assembler
42 import Harpy.X86Disassembler
43 import Foreign
44 import Control.Monad
45 import Control.Monad.Trans
46 import Data.List 
47 \end{code}
48
49 The following module system hackery is necessary, because the
50 |Harpy.X86Assembler| module exports a method called
51 |div|, which clashes with the |div| function
52 exported by the Haskell Prelude.  The prelude |div| will be
53 hidden, but is still available as a qualified name.
54
55 \begin{code}
56 import Prelude hiding (div)
57 import qualified Prelude
58 \end{code}
59
60 \subsection{Data Types}
61
62 In the following, we define several data types for representing lambda
63 calculus terms
64
65 A |Name| represents a variable name.  In a real
66 implementation, it would probably be more complicated data type for
67 handling qualified or compiler-generated names.  For now, a string
68 will suffice.
69
70 \begin{code}
71 type Name = String
72 \end{code}
73
74 In our implementation, a variable may refer to (a) a global variable,
75 which is represented by its address, (b) a parameter, which is
76 represented by the number of enclosing lambda expression, or (c) a
77 free variable, which is represented by its index into the current code
78 closure.
79
80 \begin{code}
81 data VarLoc  =  Global Word32
82              |  Param Int
83              |  Free Int
84              deriving (Show)
85 \end{code}
86
87 A compile-time environment represents a mapping from variable names to
88 variable locations.
89
90 \begin{code}
91 data Env = Env [(Name, VarLoc)]
92 \end{code}
93
94 An expression is represented by the following data type and may be a
95 variable, an immediate value (integer constant), a lambda abstraction
96 or an application expression.
97
98 \begin{code}
99 data Exp  =  Var Name
100           |  Imm Int
101           |  Abs Name Exp
102           |  App Exp Exp
103 \end{code}
104
105 The |State| type represents the state of a running program.
106 It consists of a pointer to the next available word of heap memory,
107 and a pointer to the end of the heap.  These two values are necessary
108 for dynamically allocating memory and for performing heap-overflow
109 checks.
110
111 \begin{code}
112 data State = State {  heap     :: Ptr Word32,
113                       heapEnd  :: Ptr Word32}
114 \end{code}
115
116 The following test expressions are constructed using the constructors of
117 type |Exp| and are to be evaluated by the main program.
118
119 \begin{code}
120 testExp0 = App (Abs "x" (Var "x")) (Imm 12)
121 testExp1 = App (App (Abs "x" (Abs "y" (Var "x"))) (Imm 12)) (Imm 23)
122 \end{code}
123
124 \subsection{Main Program}
125
126 Before presenting the compiler, we will have a look at how it is used.
127 The entry point to the dynamic compiler is the function
128 |interpret|, which takes an expression and returns the value
129 calculated by the expression.  The main program simply prints the
130 result.
131
132 \begin{code}
133 $(callDecl "callFunc" [t|Word32|])
134 \end{code}
135
136 \begin{code}
137 main :: IO ()
138 main = do  res <- interpret testExp1
139            putStrLn $ "Result: " ++ show res
140 \end{code}
141
142 The |interpret| function allocates 16 kbytes of heap and
143 compiles the expression.  The |State| of the compiler is
144 passed to the |runCodeGen| function as a user state.
145
146 \begin{code}
147 interpret :: Exp -> IO Word32
148 interpret exp =
149     do  let heapSize = 1024 * 16
150         heap <- mallocBytes heapSize
151         (_, Right res) <- runCodeGen (compileTop exp) (Env []) 
152                           (State heap (heap `plusPtr` 
153                                        (heapSize `Prelude.div` 4)))
154         return res
155 \end{code}
156
157 \subsection{Compilation}
158
159 The compilation starts in the function |compileTop|, which emits code
160 for creating a stack frame, saving all general-purpose registers
161 (except \verb|eax|, which will contain the result of the execution),
162 and finally compiles the expression.  Afterwards, all registers are
163 restored and the function is called.  In addition we call the
164 disassembler on the generated code and print it out.  This is a useful
165 debuggin aid when generating assembler code.
166
167 \begin{code}
168 compileTop :: Exp -> CodeGen Env State Word32
169 compileTop exp =
170     do  st <- getState
171         push ebp
172         mov ebp esp
173         push ebx
174         push ecx
175         push edi
176         push esi
177         mov ecx ((fromIntegral (ptrToWordPtr (heap st))) :: Word32)
178         compile exp
179         pop esi
180         pop edi
181         pop ecx
182         pop ebx
183         mov esp ebp
184         pop ebp
185         ret
186         y <- callFunc
187         dis <- disassemble
188         liftIO $ mapM_ (putStrLn . showIntel) dis
189         return y
190
191 \end{code}
192
193 \subsubsection{Handling Variables}
194
195 The |findVar| function looks up a variable in the
196 environment and returns its binding.
197
198 \begin{code}
199 findVar s = 
200     do  Env e <- getEnv
201         case lookup s e of
202           Just vl -> return vl
203           Nothing -> error ("unbound variable: " ++ s)
204 \end{code}
205
206 For the implementation of closures, we need to calculate free
207 variables of expressions, so that we know what to store into closures
208 and how to access free variables from the body of a lambda expression.
209
210 \begin{code}
211 freeVariables (Var s) = return [s]
212 freeVariables (Imm _) = return []
213 freeVariables (Abs x b) = liftM (delete x) (freeVariables b)
214 freeVariables (App e1 e2) = liftM2 union (freeVariables e1) (freeVariables e2)
215 \end{code}
216
217 \subsubsection{Heap Allocation}
218
219 Closures are the only dynamically allocated structures in our little
220 compiler.  They are allocated from a contiguous block of malloc'ed
221 memory, which is passed in the code generator monad's state.  The
222 following function generates code for allocating $w$ words of memory
223 in the heap, and returning a pointer to the memory in register
224 \verb|eax|.  On heap overflow, a breakpoint instruction is executed.
225
226 \begin{code}
227 emitAlloc w =
228     do  mov eax ecx
229         st <- getState
230         cmp ecx (fromIntegral (ptrToWordPtr (heapEnd st)) :: Word32)
231         next <- newLabel
232         jl next
233         breakpoint
234         defineLabel next
235         add ecx ((4 * w) :: Word32)
236 \end{code}
237
238 \subsubsection{The Compilation Proper}
239
240 Finally, the |compile| function compiles an expression.
241 Constants are simply loaded into the result register, values of
242 variables are retrieved from their respective addresses (global
243 variables from absolute addresses, parameters relative to the stack
244 base pointer, and free variables relative to the closure pointer.
245
246 \begin{code}
247 compile :: Exp -> CodeGen Env State ()
248 compile (Imm i) = 
249     do  mov eax (fromIntegral i :: Word32)
250 compile (Var s) =
251     do  c <- findVar s
252         case c of
253           Global addr -> mov eax (Addr addr)
254           Param ofs -> mov eax (Disp (fromIntegral ofs), ebp)
255           Free ofs -> mov eax (Disp (fromIntegral ofs), esi)
256 \end{code}
257
258 Lambda expressions are more complicated.  We first need to calculate
259 the set of free variables of the body expression.  Then the body of
260 the expression is compiled (with a jump around its code, so that it is
261 not actually executed at this point).  Then a closure record is
262 allocated on the heap, a code pointer to the body is stored in the
263 first word, and the values of all free variables of the body are
264 calculated and moved into the remaining fields of the closure.
265
266 The result is a pointer to the new closure, returned in \verb|eax|, as
267 usual.
268
269 \begin{code}
270 compile exp@(Abs x body) =
271     do  fv <- freeVariables exp
272         let frees = zip fv (map Free [4,8..])
273         next <- newLabel
274         jmp next
275         f <- setLabel
276         push ebp
277         mov ebp esp
278         mov esi (Disp 8, ebp)
279         withEnv (Env ((x, Param 12) : frees)) (compile body)
280         mov esp ebp
281         pop ebp
282         ret
283         defineLabel next
284         emitAlloc (fromIntegral (length frees + 1))
285         mov edi eax
286         mov (Disp 0, edi) f
287         if length frees > 0
288            then do  push eax
289                     mapM_ (\ (x, Free ofs) -> 
290                            do  compile (Var x)
291                                mov (Disp (fromIntegral ofs), edi) eax)
292                       frees
293                     pop eax
294            else return ()
295 compile (App e1 e2) = 
296     do  compile e2
297         push eax
298         compile e1
299         push eax
300         call (Disp 0, eax)
301         add esp (8 :: Word32)
302 \end{code}
303
304 \section{Conclusion}
305
306 This completes our little just-in-time compiled lambda calculus
307 evaluator.  We hope that this tutorial makes clear many of the fine
308 points in using the library.
309
310 Happy Harpy Hacking in Haskell!
311
312 \end{document}