2eaa1c4fb4f4abaef71d53d8e095f18c3a673b38
[barrelfish] / tools / flounder / Syntax.lhs
1 %include polycode.fmt
2
3 %if false
4   Flounder2: an even more simpler IDL for Barrelfish
5    
6   Copyright (c) 2009 ETH Zurich.
7   All rights reserved.
8   
9   This file is distributed under the terms in the attached LICENSE file.
10   If you do not find this file, copies can be found by writing to:
11   ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
12 %endif
13
14
15 \section{The Abstract Syntax}
16
17 In this module, we define the combinators to embed the Flounder
18 language into Haskell. So, we will mix the design the Abstract-Syntax
19 Tree with the definition of some handy combinators.
20
21 > module Syntax where
22
23
24 \subsection{Interface Header}
25
26
27 First, we define the abstract syntax of our embedded language. At the
28 top-level is the \emph{interface} definition. It consists of a @name@
29 and, potentially, a @description@. It contains a list of
30 \emph{declarations}.
31
32 > data Interface = Interface String (Maybe String) [ Declaration ] 
33 >
34 > generalInterface :: Maybe String -> String -> [ Declaration ] -> Interface
35 > generalInterface description name declarations = 
36 >     Interface name description declarations
37
38 Which can be further refined into an anonymous interface, ie. with no
39 description:
40
41 > aInterface :: String -> [Declaration] -> Interface
42 > aInterface = generalInterface Nothing
43
44 And, the more common, a documented interface:
45
46 > interface :: String -> String -> [Declaration] -> Interface
47 > interface name description declarations = 
48 >     generalInterface (Just description) name declarations
49
50 Finally, various getters:
51
52 > interfaceName :: Interface -> String
53 > interfaceName (Interface name _ _) = name
54
55 \subsection{Declarations}
56
57 A declaration is either a \emph{type definition} or a \emph{message
58 definition}. In the next subsections, we define these terms in turn.
59
60 > data Declaration = Typedef TypeDef
61 >                  | Messagedef MessageDef
62
63
64 \subsubsection{Declaring types}
65
66
67 We can define new types out of existing ones thanks to five
68 constructs:
69 \begin{description}
70         \item[Structure:] like C @struct@, it defines a name-indexed record
71         \item[Array:] defines a static array of elements of a given type
72         \item[Enumeration:] like C @enum@, defines a sum-type over some elements
73         \item[Alias:] redefine the name of an already defined type
74 \end{description}
75
76 > data TypeDef = TStruct String [StructField]
77 >              | TArray TypeRef String Integer
78 >              | TEnum String [String] 
79 >              | TAlias String TypeRef
80 >              | TAliasT String TypeBuiltin
81
82 In this definition, we notice the presence of @TypeRef@: indeed, when
83 we construct a new type, it can use either built-in types, such as
84 @uint8_t@, or previously defined types, identified by their name.
85
86 > data TypeRef = Builtin TypeBuiltin
87 >              | TypeVar String
88 >              | TypeAlias String TypeBuiltin
89 >     deriving (Show)
90
91 The builtin types being:
92
93 > data TypeBuiltin = UInt8
94 >                  | UInt16
95 >                  | UInt32
96 >                  | UInt64
97 >                  | UIntPtr
98 >                  | Int8
99 >                  | Int16
100 >                  | Int32
101 >                  | Int64
102 >                  | IntPtr
103 >                  | Size
104 >                  | Char
105 >                  | Bool
106 >                  | String
107 >                  | IRef
108 >                  | Cap
109 >                  | GiveAwayCap
110 >                    deriving (Enum, Eq)
111
112 Which are shown with:
113
114 > instance Show TypeBuiltin where
115 >     show UInt8 = "uint8"
116 >     show UInt16 = "uint16"
117 >     show UInt32 = "uint32"
118 >     show UInt64 = "uint64"
119 >     show UIntPtr = "uintptr"
120 >     show Int8 = "int8"
121 >     show Int16 = "int16"
122 >     show Int32 = "int32"
123 >     show Int64 = "int64"
124 >     show IntPtr = "intptr"
125 >     show Size = "size"
126 >     show Bool = "bool"
127 >     show String = "string"
128 >     show Char = "char"
129 >     show IRef = "iref"
130 >     show Cap = "cap"
131 >     show GiveAwayCap = "give_away_cap"
132
133 > instance Read TypeBuiltin where
134 >     readsPrec _ = \s -> case s of 
135 >                                "uint8" -> [(UInt8, "")]
136 >                                "uint16" -> [(UInt16, "")]
137 >                                "uint32" -> [(UInt32, "")]
138 >                                "uint64" -> [(UInt64, "")]
139 >                                "uintptr" -> [(UIntPtr, "")]
140 >                                "int8" -> [(Int8, "")]
141 >                                "int16" -> [(Int16, "")]
142 >                                "int32" -> [(Int32, "")]
143 >                                "int64" -> [(Int64, "")]
144 >                                "intptr" -> [(IntPtr, "")]
145 >                                "int" -> [(Int32, "")] -- XXX: why? -AB
146 >                                "size" -> [(Size, "")]
147 >                                "bool" -> [(Bool, "")]
148 >                                "string" -> [(String, "")]
149 >                                "char" -> [(Char, "")]
150 >                                "iref" -> [(IRef, "")]
151 >                                "cap" -> [(Cap, "")]
152 >                                "give_away_cap" -> [(GiveAwayCap, "")]
153 >                                _ -> error  $ "Undefined builtin type " ++ s
154
155 Hence, we can define:
156
157 > isBuiltin :: TypeRef -> Bool
158 > isBuiltin (Builtin _) = True
159 > isBuiltin _ = False
160
161 And the usual combinators:
162
163 > uint8, uint16, uint32, uint64, uintptr :: TypeRef
164 > uint8 = Builtin UInt8
165 > uint16 = Builtin UInt16
166 > uint32 = Builtin UInt32
167 > uint64 = Builtin UInt64
168 > uintptr = Builtin UIntPtr
169
170 > int8, int16, int32, int64, intptr :: TypeRef
171 > int8 = Builtin Int8
172 > int16 = Builtin Int16
173 > int32 = Builtin Int32
174 > int64 = Builtin Int64
175 > intptr = Builtin IntPtr
176
177 > size, string, iref, cap, give_away_cap :: TypeRef
178 > size = Builtin Size
179 > string = Builtin String
180 > iref = Builtin IRef
181 > cap = Builtin Cap
182 > give_away_cap = Builtin GiveAwayCap
183
184 > var :: String -> TypeRef
185 > var typeRef = TypeVar typeRef
186
187 > als :: String -> TypeBuiltin -> TypeRef
188 > als typeRef origin = TypeAlias typeRef origin
189
190 Then, we can build a type definition out of these special cases with:
191
192 > typedef :: TypeDef -> Declaration
193 > typedef typeDefinition = Typedef typeDefinition
194
195
196
197 Here's a utility function to resolve a named type (which may be an alias) to
198 its canonical definition:
199
200 > lookup_type_name :: [TypeDef] -> String -> TypeDef
201 > lookup_type_name types name = case def of
202 >         -- FIXME: these types seem a bit confusing -AB
203 >         -- why are there so many ways to specify an alias of a builtin?
204 >         (TAlias _ (Builtin b)) -> TAliasT name b
205 >         (TAlias _ (TypeVar v)) -> lookup_type_name types v
206 >         (TAlias _ (TypeAlias _ b)) -> TAliasT name b
207 >         d -> d
208 >     where
209 >         -- I'm assuming there must be exactly one definition for the type name
210 >         def
211 >             | null defs = error $ "lookup_type_name: " ++ name ++ " not defined"
212 >             | null $ tail defs = head defs
213 >             | otherwise = error $ "lookup_type_name: " ++ name ++ " multiply defined"
214 >         defs = [t | t <- types, typedef_name t == name]
215
216 >         typedef_name :: TypeDef -> String
217 >         typedef_name (TStruct n _) = n
218 >         typedef_name (TArray _ n _) = n
219 >         typedef_name (TEnum n _) = n
220 >         typedef_name (TAlias n _) = n
221 >         typedef_name (TAliasT n _) = n
222
223 As above, but for a TypeRef:
224
225 > lookup_typeref :: [TypeDef] -> TypeRef -> TypeDef
226 > lookup_typeref _ (Builtin b) = TAliasT (show b) b
227 > lookup_typeref _ (TypeAlias n b) = TAliasT n b
228 > lookup_typeref types (TypeVar v) = lookup_type_name types v
229
230
231
232 \paragraph{Structure}
233
234 So, a @struct@ is identified by its @name@, which, as in C, comes
235 after a list of @fields@.
236
237 > struct :: [StructField] -> String -> TypeDef
238 > struct fields name = TStruct name fields
239
240 The fields of a structure consist of a type @typeField@ associated
241 with a field @name@.
242
243 > data StructField = TStructField TypeRef String
244 >
245 > field, (.@@.) :: TypeRef -> String -> StructField
246 > field typeField name = TStructField typeField name
247 > (.@@.) = field
248
249 \paragraph{Array}
250
251 An array is identified by a @name@ and defined by the type of its
252 elements, @typeElts@, as well as its length.
253
254 > array :: TypeRef -> String -> Integer -> TypeDef
255 > array typeElts name length = TArray typeElts name length
256
257 \paragraph{Enumeration}
258
259 An enumeration is, as always, identified by a @name@. The content of
260 an enumeration is a list of tags, the @elements@.
261
262 > enum :: [String] -> String -> TypeDef
263 > enum elements name = TEnum name elements
264
265 \paragraph{Aliasing}
266
267 Finally, we can do type aliasing: we can give a @newName@ to a type,
268 which was previously known as @originalName@. Note that the names are
269 switched between the combinator and the data-type.
270
271 > alias :: TypeRef -> String -> TypeDef
272 > alias originalName newName = TAlias newName originalName
273
274
275
276 \subsubsection{Declaring a Message}
277
278
279 A @message@ is identified by a @name@ and is either a @Call@, a
280 @Response@, or it is a @Message@, in all generality. A message can
281 carry some arguments, which are described by a list of
282 @MessageArgument@, in @msgArgs@. Hence the following definition:
283
284 > data MessageDef = Message MessageType String [ MessageArgument ] [(String, [(String, MetaArgument)])]
285 >                 | RPC String [ RPCArgument ] [(String, [(String, MetaArgument)])]
286 >
287 > data MessageType = MMessage 
288 >                  | MCall
289 >                  | MResponse
290 >
291 > message, call, response :: String -> [ MessageArgument ] -> Declaration
292 > message name args = Messagedef $ Message MMessage name args []
293 > call name args = Messagedef $ Message MCall name args []
294 > response name args = Messagedef $ Message MResponse name args []
295
296 As for the arguments passed to a message, they are simply the type @typeArg@ and
297 the @identifier@ of the argument:
298
299 > data MessageArgument = Arg TypeRef Variable
300 >     deriving (Show)
301 >
302 > data Variable = Name String
303 >               | DynamicArray String String
304 >     deriving (Show)
305 >
306 > arg, (.@.) :: TypeRef -> String -> MessageArgument
307 > arg typeArg identifier = Arg typeArg (Name identifier)
308 > (.@.) = arg
309 >
310 > argDynamic, (.#.) :: TypeRef -> (String, String) -> MessageArgument
311 > argDynamic typeArg (identifier, length) = Arg typeArg (DynamicArray identifier length)
312 > (.#.) = argDynamic 
313
314 And we are done for message definitions.
315
316 Concerning RPC, the RPC arguments take into account whether a
317 parameter is used \emph{in} or \emph{out}.
318
319 > data RPCArgument = RPCArgIn TypeRef Variable
320 >                  | RPCArgOut TypeRef Variable
321
322 The meta-parameters allow passing additional information to individual
323 backends. The paramaters are a mapping from names to either an identifier,
324 which should match a message argument, or a value:
325
326 > data MetaArgument = BackendInt Integer
327 >                   | BackendMsgArg String