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}