Initial commit: 0.4.3.0 from hackage
[harpy.git] / 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}