git.barrelfish.org Git - barrelfish/blob - 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