doc/tutorial.lhs

   1 \documentclass[a4paper]{article}
   2
   3 \usepackage[latin1]{inputenc}
   4
   5 \usepackage{listings}
   6
   7 \lstnewenvironment{code}{}{}
   8 \lstset{
   9   basicstyle=\ttfamily,
  10   keywordstyle=\normalfont\bfseries,
  11   identifierstyle=\bfseries,
  12   commentstyle=\rmfamily,
  13   texcl=true,
  14   language=Haskell,
  15   flexiblecolumns=false,
  16   basewidth={0.5em,0.45em},
  17   extendedchars=true,
  18   frame=leftline,
  19   numbers=left,
  20   firstnumber=last,
  21   literate={+}{{$+$}}1 {/}{{$/$}}1 {*}{{$*$}}1 {=}{{$=$}}1
  22            {>}{{$>$}}1 {<}{{$<$}}1
  23            {->}{{$\rightarrow$}}2 {>=}{{$\geq$}}2 {<-}{{$\leftarrow$}}2
  24            {<=}{{$\leq$}}2 {=>}{{$\Rightarrow$}}2 {\ .}{{ $\circ$}}2,
  25   numberstyle=\tiny
  26 }
  27
  28 \title{Harpy Tutorial}
  29 \author{Martin Grabmüller \and Dirk Kleeblatt}
  30
  31 \begin{document}
  32 \maketitle
  33 \abstract{
  34 We present some of the features of
  35 Harpy, an in-line assembler for Haskell.  This little tutorial shows how to
  36 write assembler programs without making one's hands dirty, staying in the
  37 beautiful pure functional world of Haskell.  During this tutorial, we develop
  38 step by step an assembler implementation of the factorial function, and show
  39 how assembler code can be called from ordinary Haskell code.
  40
  41 This document is written as a literate Haskell program, so you can compile and run it
  42 without any modifications.
  43 }
  44
  45 \section{Introduction}
  46
  47 To make use of Harpy and (a subset of) the x86 assembler instructions, we need
  48 to import some modules.
  49
  50 \begin{code}
  51 import Harpy.CodeGenMonad
  52 import Harpy.X86Assembler
  53 import Foreign
  54 import Control.Monad.Trans
  55 \end{code}
  56
  57 The module \lstinline-Harpy.CodeGenMonad- defines the polymorphic type
  58 \lstinline-CodeGen e s-, which is an instance of the \lstinline-Monad-
  59 class. The type parameters \lstinline-e- and \lstinline-s- can be instantiated
  60 to the type of an user's environment and state, respectively. These behave
  61 like the environments and states known from the \lstinline-Reader- and
  62 \lstinline-State- monads. Besides this monadic type, this module defines some
  63 functions to make use of code labels, and provides an interface to a
  64 disassembler.
  65
  66 The module \lstinline-Harpy.X86Assembler- provides a subset of the x86
  67 assembler instructions, e.~g. \verb-mov- for moving memory words around. These
  68 instructions are implemented as class methods, to allow different addressing
  69 modes without hassle.
  70
  71 We additionally import the module \lstinline-Foreign-, since we need some low
  72 level types to exchange parameters and results with our assembler code, and
  73 \lstinline-Control.Monad.MonadTrans- to have some instances available.
  74
  75 \section{A fast factorial function}
  76
  77 Now we are ready to define the factorial function in assembler code.
  78
  79 \lstset{firstnumber=4}
  80 \begin{code}
  81 fac :: CodeGen e s ()
  82 fac = do loopTest  <- newLabel
  83          loopStart <- newLabel
  84          ensureBufferSize 160
  85          push ecx
  86          mov  ecx (Disp 8, esp)
  87          mov  eax (1 :: Word32)
  88          jmp  loopTest
  89          loopStart @@ mul ecx
  90          sub  ecx (1 :: Word32)
  91          loopTest @@ cmp ecx (0 :: Word32)
  92          jne  loopStart
  93          pop  ecx
  94          ret
  95 \end{code}
  96
  97 We first create two labels, \lstinline-loopTest- and \lstinline-loopStart-, to
  98 mark the test and the beginning of a loop. In lines 5 and 6, these labels are
  99 merely announced to Harpy, they are not (yet) defined to sit at a specific
 100 code position.
 101
 102 Line 8 saves the \lstinline-ecx- rigister on the system stack, because we will
 103 use it as a loop counter, and want to restore it before returning to Haskell
 104 functions.
 105
 106 Line 9 shows an indirect adressing with displacement. Note, that all Harpy
 107 functions use Intel assembler style, i.~e. the first operand is the
 108 destination and the second one the source of each instruction. So this line
 109 moves the memory contents at address \lstinline-esp+8- into
 110 \lstinline-ecx-. Since we will make a C call into our assembler code, this
 111 accesses the first parameter on the stack. When returning to the Haskell world
 112 via \lstinline-ret-, we leave our result in \lstinline-eax-, again adhering to
 113 the C calling convention.
 114
 115 The rest of \lstinline-fac- just accumulates the factorial in \lstinline-eax-
 116 while counting down \lstinline-ecx-. Lines 12 and 14 show how our labels
 117 \lstinline-loopStart- and \lstinline-loopTest- are placed at specific code
 118 positions.
 119
 120 The function \lstinline-fac- is not really our wanted factorial
 121 function. Instead it is a monadic command that, when executed, writes
 122 assembler code into a buffer. To ensure, that this buffer is always large
 123 enough to hold the generated instruction, you have to sprinkle your code with
 124 calls to \lstinline-ensureBufferSize-. In line 7 we make sure that 160 bytes
 125 are available, which is enough for our 10 instructions. As a rule of thumb, no
 126 instruction can be larger than 16 bytes, so the number of assembler
 127 instructions times 16 is a safe upper bound.
 128
 129 The next section shows how to prepare a call into such a buffer.
 130
 131 \section{Preparing a call}
 132
 133 The module \lstinline-Harpy.Call- defines some functions to call functions
 134 written in assembler with various argument and result types. But since it is
 135 possible to use all types suitable for FFI calls as argument or result, sooner
 136 or later you will need some combination not yet implemented. So here we show
 137 how to define your own calling stub.
 138
 139 \lstset{firstnumber=18}
 140 \begin{code}
 141 $(callDecl "callFac" [t|Word32 -> Word32|])
 142 \end{code}
 143
 144 The Template Haskell function \lstinline-callDecl- is used to declare a
 145 function \lstinline-callFac- which will call our assembler fragment. We want
 146 to pass a parameter of type \lstinline-Word32-, and expect a result of the
 147 same type, that's why we give \lstinline+Word32 -> Word32+ as argument to
 148 \lstinline-callDecl-. If you wonder about the fancy \lstinline-$- and
 149 \lstinline-[t| |]-, either look them up in the Template Haskell
 150 documentation, or just ignore them. However, to make this line compile, you
 151 have to switch on Template Haskell, which is done for the Glasgow Haskell
 152 compiler by the command line flag \verb+-fth+.
 153
 154 \section{Calling \lstinline-fac-}
 155
 156 Now we have all we need to call into our factorial function.
 157
 158 \lstset{firstnumber=19}
 159 \begin{code}
 160 runFac :: CodeGen e s ()
 161 runFac = do fac
 162             x <- liftIO readLn
 163             y <- callFac x
 164             liftIO (putStrLn (show y))
 165 \end{code}
 166
 167 We first call \lstinline-fac- to write our assembler code into the internal
 168 buffer. Since the \lstinline-CodeGen- monad ist an instance of
 169 \lstinline-MonadIO-, we can use \lstinline-liftIO- to use all commands we wish
 170 from the \lstinline-IO- monad. Here, we use this to read the argument to the
 171 factorial function from the keyboard, and to write the result back to the
 172 screen. Line 21 calls into the internal code buffer with our assembler
 173 instructions using the stub declared in the last section.
 174
 175 \section{How to use it}
 176
 177 Up to now, all our functions live in the \lstinline-CodeGen- monad. To make
 178 use of them, we have to \emph{unlift} them into the \lstinline-IO- monad. This
 179 is done by \lstinline-runCodeGen-.
 180
 181 \lstset{firstnumber=24}
 182 \begin{code}
 183 main :: IO ()
 184 main = do
 185    (finalState, result) <- runCodeGen runFac () ()
 186    case result of
 187      Right () -> return ()
 188      Left err -> putStrLn (show err)
 189 \end{code}
 190
 191 The second and third arguments to \lstinline-runCodeGen- are the initial
 192 environment and state. Since we did not use them, their type is polymorphic
 193 and we can use \lstinline-()- as initial values. The result is a pair
 194 consisting of the final state, and a result value. A value constructed with
 195 the constructor \lstinline-Right- indicates a successful run, while
 196 \lstinline-Left- values indicate runtime errors. These might occur for
 197 instance because of infeasible addressing modes.
 198
 199  \end{document}