@SysInclude { report } @SysInclude { tbl } @SysInclude { haskell } def @SectionLink right sec {sec @CrossLink {section @NumberOf sec}} @Report @InitialSpace {tex} # Treat multiple spaces as one @Title {From Haskell to VHDL} @Author {Matthijs Kooijman} @Institution {University of Twente} @DateLine {Yes} @CoverSheet {No} # @OptimizePages {Yes} // @Section @Title {Introduction} @Begin @LP The aim of this project is to design a structural hardware description language, embedded in the functional language Haskell. This means that a program written in (a subset of) Haskell will be translated into hardware, using a VHDL description. The original Haskell program is a structural description, meaning that the programmer explicitly specifies hardware and area vs time trade-offs are already made explicit in the description and the translator is not required to do any scheduling. @LP The compilation process is divided roughly into four steps: @LeftList @ParagraphItem { Parsing, typechecking and simplifying the Haskell source(s). By using the API that GHC makes available, this step is fairly easy. We can feed a Haskell source file into GHC, which then performs all the neccesary steps to create a @I Core module, which is a simplified representation of the Haskell source file.} @ParagraphItem { Flattening the function that is the top of the design, and (recursively) any functions it requires. Flattening is the process of removing nesting from expressions in the functions and making the routes values take through an expression more explicit. This results in a flat list of flat functions.} @ParagraphItem { Processing the flattened functions. This step does transformations such as deciding which function arguments will be used as state values, decide names for signals, etc.} @ParagraphItem { Translate the flat functions generated so far into VHDL. This is a fairly direct translation, all information should be present by now.} @EndList @LP In this document we will focus on the second step. The first step is completely handled by GHC and results in a Core module. The representation GHC uses for the Core language is the subject of @SectionLink {Core}. The second step translates a Core module to a set of flat functions. The representation of a flat function is the subject of @SectionLink {FlatFunctions}. The fourth step is also partly discussed in this section. Finally, the actual flattening that happens in the second step is the subject of @SectionLink {Flattening}. The third step remains undiscussed for now. @End @Section @Section @Title { The Core language } @Tag {Core} @Begin @LP GHC uses an internal representation for Haskell programs called @I {Core} . Core is essentially a small programming language, but we focus on the representation GHC uses. Inside GHC a Core program is stored using a number of custom data types, which we will describe here. @LP The descriptions given here are therefore very similar to Haskell source, and can usually be interpreted as such. To simplify this discussion, some details that are irrelevant from our point of view are left out, but each of these simplifications is noted in the text. @LP There are two main aspects of Core: Its typing system and its bindings and expression structure. @LP So far, I've focussed on the expression signature without looking closely at the typing structure, except where needed. Thus, I will describe the expression structure a bit here and provide examples to show the relation with Haskell source programs. @BeginSubSections @SubSection @Title { Core bindings } @Begin @LP A central role in the core language is played by the @I binding. A binding binds one or more expressions to one or more identifiers (@I binders). A core program is essentially a set of bindings, each of which bind to an identifier on global scope (i.e., you get one binding for each function that is defined). The @I CoreBind type is defined as follows: @ID @Haskell { NonRec CoreBndr CoreExpr | Rec [(CoreBndr, CoreExpr)] } @LP The @I NonRec constructor is the simplest: It binds a single expression to a single binder. The @I Rec constructors takes a list of binder, expression pairs, and binds each expression to the corresponding binder. These bindings happen on the same scope level, meaning that each expression can use any of the (other) bindings, creating mutually recursive references. @LP When a program is initially compiled to Core, it consists of a single @I Rec binding, containing all the bindings in the original haskell source. These bindings are allowed to reference each other, possibly recursively, but might not. One of the Core simplification passes splits out this large @I Rec constructor into as much small @I Recs and @I NonRecs as possible. @LP The @I CoreBnder type is used in @I Let expressions as well, see below. @End @SubSection @SubSection @Title { Core expressions } @Begin @LP The main expression type is @I CoreExpr, @FootNote {In reality, @I CoreExpr is an alias for @I {Expr CoreBndr}, but different types of binders are only used by GHC internally.} which has the following constructors @FootNote{The @I Note constructor was omitted, since it only serves as annotation and does not influence semantics of the expression.}. @DP @Tbl aformat { @Cell @I A | @Cell B } { @Rowa A {Var Id} B {A variable reference} @Rowa A {Lit Literal} B {A literal value} @Rowa A {App CoreExpr CoreExpr} B {An application. The first expression is the function or data constructor to apply, the second expression is the argument to apply the function to. Function application always applies a single argument, for functions with multiple arguments application is applied recursively.} @Rowa A {Lam CoreBndr CoreExpr} B {A lambda expression. When this expression is applied to some argument, the argument is bound to the binder given and the result is the given expression. Or, slightly more formal, the result is the given expression with all @I Var expressions corresponding to the binder replaced with the argument the entire lambda is applied to.} @Rowa A {Let CoreBind CoreExpr} B { A let expression. The given bind is one or more binder, expression pairs. Each expression is evaluated and bound to the corresponding binder. The result is of the entire let expression is then the given expression. @DP Or, slightly more formal, evaluates all expressions inside the given bind and returns the given expression with all @I Var expressions corresponding to the binders in the given bind replaced by their respective evaluated expressions. } @Rowa A { Case CoreExpr [CoreAlt] @FootNote {In reality, there are also another Type and CoreBndr arguments. However, the Type argument only contains the type of the entire expression, and thus is redundant and not useful for our purpose. The CoreBndr is a binder to which the scrutinee is bound, but seems this is only used for forcing evaluation of a term. Therefore, these two are left out in this discussion.} } B { A case expression, which can be used to do conditional evaluation and data type ``unpacking''. The given expression (``scrutinee'') is evaluated, bound to the given binder and depending on its value on of the CoreAlts is chosen whose expression is returned. @DP A @I CoreAlt is a three tuple describing the alternative: @IndentedDisplay @I {(AltCon, [CoreBndr], CoreExpr)} @DP Here, the @I AltCon is an alternative constructor which can matched to the scrutinee. An alternative constructor can be one of the default alternative (which matches any value not matched by other alternative constructors in the list), a literal (which matches if the scrutinee evaluates to a literal or a data constructor, which matches if the value is constructed using that specific data constructor. @DP In the last case, when a data constructor is used for the alternative, the arguments to the data constructor are extracted from the scrutinee and bound to the corresponding binders (from the second element of the @I CoreAlt tuple). @DP The last element from the tuple is the expression to return, with the extra bindings in effect. } @Rowa A { Cast CoreExpr Type } B { Cast the given expression to the given type. This plays an import role when working with @F newtype declarations and type classes. The exact workings of this expression are a bit shady, but for now we can get away with ignore it. } @Rowa A { Type Type } B { This expression turns a type into an expression, so it can be applied to functions to implement polymorphic functions and type classes. It cannot be used anywhere else. Again, we can can get away with ignore this expression for now. } } @DP @BeginSubSubSections @SubSubSection @Title {Examples} @Tag {CoreExamples} @Begin @LP To get a clearer example of how Haskell programs translate to the Core language, a number of programs are given in both Haskell syntax and the equivalent core representation. These are all simple examples, focused on showing a particular aspect of the Core language. @LP In these examples, we will use the following data type. Since most of the primitive datatypes and operators are involved in some kind of polymorphism (Even the + operator is tricky), those are less useful for simple examples. Using the following @I Bit datatype will also make these examples more appropriate for our goals. @ID @Haskell { data Bit = High | Low } @Display @Heading {Fixed value} @LP This is a trivial example which shows a simple data constructor without arguments bound to the binders ``high'' and ``low''. Note that in reality, the binder and @I Id values in @I Var nodes include some extra info about the module it is defined in and what kind of identifier it is, but that is left out here for simplicity. @CNP @ID @Example @Title {Haskell code} { @LP @Haskell { high = High low = Low}} @LP This haskell source results in the following list of @I CoreBndrs. @CNP @ID @Example @Title {Core Structure} { @LP @Haskell { [ NonRec ``high'' (Var High) , NonRec ``low'; (Var Low)]}} @LP In subsequent examples I will leave out the @I NonRec constructor and binder name and just show the resulting @I CoreExpr. @Display @Heading {Function arguments} This example shows a simple function that simply returns its argument. @CNP @ID @Example @Title {Haskell code} { @LP @Haskell { wire :: Bit -> Bit wire a = a}} @CNP @ID @Example @Title {Core Structure} { @LP @Haskell { Lam a (Var a)}} @Display @Heading { Pattern matching } This example shows a function with a single argument which uses pattern matching, which results in a simple case statement. @CNP @ID @Example @Title {Haskell Code} { @LP @Haskell { inv :: Bit -> Bit inv High = Low inv Low = High}} @ID @Example @Title {Core Structure} { @LP @Haskell { Lam ds (Case (Var ds) [ (High, [], (Var Low)), (Low, [], (Var High)) ] )}} @LP Note that in the tuples describing the alternatives, the first element is a data constructor directly, while the third argument is an expression referring to a dataconstructor (henc the Var constructor). @Display @Heading {Function application} This example shows a function that applies other functions (with one and two arguments) to its own arguments to do its work. It also illustrates functions accepting multiple arguments. @LP For this example we assume there is a function @I nand available to returns the negated and of its two arguments. @CNP @ID @Example @Title {Haskell code} { @LP @Haskell { or :: Bit -> Bit -> Bit or a b = inv (nand a b)}} @CNP @ID @Example @Title {Core structure} { @LP @Haskell { Lam a (Lam b (App (Var inv) (App (App (Var nand) (Var a)) (Var b) ) ))}} @Display @Heading {Tuples} This example shows a function that accepts a tuple of two values and returns a tuple of two values again. @LP This example assumes the availability of two functions @I and and @I xor, with obvious meaning. @CNP @ID @Example @Title {Haskell code} { @LP @Haskell { -- Accepts two values and returns the sum and carry out respectively. half_adder :: (Bit, Bit) -> (Bit, Bit) half_adder (a, b) = (and a b, xor a b)}} @LP Since the core structure corresponding to this (still pretty trivial) function will be quite complex already, we will first show the desugared and simplified version of the function, to which the core structure directly corresponds. @CNP @ID @Example @Title {Simplified haskell code} { @LP @Haskell { half_adder = \ds -> Case ds of (a, b) -> (,) (and a b) (xor a b) }} @CNP @ID @Example @Title {Core structure} { @LP @Haskell { Lam ds (Case (Var ds) [( (,), [a, b], (App (App (Var (,)) (App (App (Var and) (Var a) ) (Var b) ) ) (App (App (Var xor) (Var a) ) (Var b) ) ) )] )}} @LP Note the (,) in this example, which is the data constructor for a two-tuple. It can be passed two values and will construct a tuple from them. @FootNote {In reality, this dataconstructor takes @I four arguments, namely the types of each of the elements and then the elements themselves. This is because the two-tuple type really takes type arguments, which are made explicit on every call to its data constructors.} @Display @Heading {Let expressions} This example shows a function that uses a let expression to use a value twice. @CNP @ID @Example @Title {Haskell code} { @LP @Haskell { f :: Bit -> (Bit, Bit) f a = (x, and a x) where x = xor a a}} @CNP @ID @Example @Title {Simplified haskell code} { @LP @Haskell { f = \a -> let x = xor a a in (,) x (and a x) }} @CNP @ID @Example @Title {Core structure} { @LP @Haskell { Lam a (Let [(NonRec x (App (App (Var xor) (Var a) ) (Var a) ) )] (App (App (Var (,)) (Var x) ) (App (App (Var and) (Var a) ) (Var x) ) ) )}} @Display @Heading {Pattern matching} This example shows a multiplexer, i.e., a function that selects one of two inputs, based on a third input. This illustrates how pattern matching is translated into core and can be used to create conditional signal connections. @CNP @ID @Example @Title {Haskell code} { @LP @Haskell { mux2 :: Bit -> (Bit, Bit) -> Bit mux2 Low (a, b) = a mux2 High (a, b) = b}} @CNP @ID @Example @Title {Simplified haskell code} { @LP @Haskell { mux2 = \ds ds1 -> case ds of Low -> case ds1 of (a, b) -> a High -> case ds1 of (a, b) -> b}} @CNP @ID @Example @Title {Core structure} { @LP @Haskell { Lam ds (Lam ds1 (Case (Var ds) [( Low, [], (Case (Var ds1) [( (,) [a, b], (Var a) )] ) ),( High, [], (Case (Var ds1) [( (,) [a, b], (Var b) )] ) )] ))}} @End @SubSubSection @EndSubSubSections @End @SubSection @EndSubSections @End @Section @Section @Title {Flat Functions} @Tag {FlatFunctions} @Begin @LP As an intermediate between Core and VHDL, we use "flat" functions (the name is open for suggestions). A flat function is a simplified version of the function, which defines a number of signals (corresponding to single haskell values) which can be used in a number of places and are defined to a single value. A single value in this case means something that will probably result in a single VHDL signal or port, so a 2-tuple results in two signals, for example. @LP The function is flat, because there are no directly nested expressions. A function application can only use signals, not nested applications or other expressions. These signals can of course be defined as the result of an expression or function application, so the original expressions can still be expressed. @LP A flat function is defined as a single @I FlatFunction constructor with the following fields @FootNote {The implementation additionally has a @I sigs fields listing all the signals, but since that list is directly deducable from the @I args and @I defs fields, it is left out here}: @DP @Tbl aformat { @Cell @I A | @Cell B } { @Rowa A {args :: [SignalMap]} B {A list that maps each argument to this function to a (number of) signal(s). In other words, this field specifies to which signals the function arguments should be assigned when this function is called.} @Rowa A {res :: SignalMap} B {A map that maps the return value to a (number of) signal(s). signal(s). In other words, this field specifies which signals contain the function result when this function is called.} @Rowa A {defs :: [SignalDef]} B {Definitions for each of the signals in the function. Each @I SignalDef defines one ore more signals, and each signal should be defined exactly once. Note that the signals in @I args don't have a @I SignalDef entry.} } @LP The type @I Signal plays a central role in a flat function. It identifies a signal. It's exact representation is not that important (the current implementation uses an Int), as long as it can be compared and unique new @I Signals can be generated. @LP The @I SignalMap type has the following two constructors: @ID @Haskell { Single Signal | Tuple [SignalMap] } @LP This means we can support any type that can be translated to a signal directly (currently only @I Bit and @I Bool) and tuples containing those types. A signal map allows us to decompose a Haskell value into individual pieces that can be used in the resulting VHDL. @LP The @I SignalDef type is slightly more complex. For one or more signals, it specifies how they are defined. In the resulting hardware, these can be mapped to simple signal assignments or port mappings on component instantiations. The type has the following constructors: @DP @Tbl aformat { @Cell @I A | @Cell B } { @Rowa A {lines @Break { FApp func :: HsFunction @FootNote {In the current implementation, this value can also be a representation of a higher order function. However, since this is not functional yet, it is left out of this discussion.} args :: [SignalMap] res :: SignalMap }} B {A function application. The function that is called is identified by the given @I HsFunction, and passed the values in the given @I SignalMaps as arguments. The result of the function will be assigned to the @I SignalMap in @I res.} @Rowa A {lines @Break { CondDef cond :: Signal true :: Signal false :: Signal res :: Signal }} B {A conditional signal definition. If the signal pointed to by @I cond is True, @I true is assigned to @I res, else @I false is assigned to @I res. The @I cond signal must thus be of type @I Bool. This keeps conditional assignment very simple, all complexity in the conditions will be put into @I SignalExpr in @I UncondDef. } @Rowa A {lines @Break { UncondDef src :: SignalExpr dst :: Signal}} B {Unconditional signal definition. In the most basic form (assigning a simple signal to another signal) this is not often useful (only in specific cases where two signals cannot be merged, when assigning an output port to an input port for example). The more interesting use for unconditional definition is when the @I SignalExpr is more complicated and allows for more complexity. } } @LD @Heading {Identifying functions} @LP To identify a function to call we use the @I HsFunction type. This type is used for two purposes. First, it contains the name of the function to call, so the corresponding @I CoreBndr and @I CoreExpr can be found in the current module. Secondly, an @I HsFunction contains information on the use of each argument and the return value. In particular, it stores for each (part of an) argument or return value if it should become an input or output Port, or a state internal to the called function. @LP The @I HsFunction type looks as follows: @ID @Haskell { HsFunction { func :: String, args :: [UseMap], res :: UseMap }} @LP Here, the UseMap type is defined similar to the @I SignalMap type @FootNote{In reality, both @I SignalMap and @I UseMap are generalized into a type @I HsValueMap which takes an element type as a type parameter}: @ID @Haskell { Single Use | Tuple [Use]} @LP The @I Use type is defined as follows. The @I StateId argument to the @I State constructor is a unique identifier for the state variable, which can be used to match input and output state variables together. This state id should be unique within either arguments or the return value, but should be matched between them (@I i.e., there should be exactly one @I State use with id 0 in the arguments, and exactly once in the return value) @FootNote{In the current implementation, there is third constructor in the @I Use type for arguments that get higher order functions passed in. Since this is not functional yet, this is left out of this discussion}. @ID @Haskell { Port | State StateId} @LP The last type used in this description is @I SignalExpr. It allows for certain expressions in the resulting VHDL, currently only comparison. The type has the following constructors: @DP @Tbl aformat { @Cell @I A | @Cell B } { @Rowa A { Sig Signal } B { A simple signal reference. } @Rowa A { Literal String } B { A literal value. The given string is the resulting VHDL value. Perhaps this should better be something less VHDL-specific, but this works for now. } @Rowa A { Eq Signal Signal } B { Equality comparison. This is the only comparison supported for now and results in a @I Bool signal that can be used in a @I CondDef. } } @BeginSubSections @SubSection @Title {Examples} @Begin @LP To ease the understanding of this datastructure, we will show the flattened equivalents of some of the examples given in @SectionLink {CoreExamples}. When reading these examples, don't forget that the signal id's themselves are interchangeable, as long as they remain unique and still link the right expressions together (@I i.e., the actual numbers are not relevant). @Display @Heading {Fixed value} @CNP @ID @Example @Title {Haskell code} { @LP @Haskell {high = High}} @LP This Haskell source results in the following @I FlatFunction. @CNP @ID @Example @Title {Flat function} { @LP @Haskell { FlatFunction { sigs = [0], args = [], res = (Single 0), defs = [UncondDef (Lit "'1'") 0] }}} @Display @Heading {Function application} @CNP @ID @Example @Title {Haskell code} { @LP @Haskell { or :: Bit -> Bit -> Bit or a b = inv (nand a b)}} @CNP @ID @Example @Title {Flat function} { @LP @Haskell { FlatFunction { sigs = [0, 1, 2, 3], args = [Single 0, Single 1], res = (Single 3), defs = [ (FApp (HsFunction "nand" [Single Port, Single Port] (Single Port)) [Single 0, Single 1] (Single 2) ), (FApp (HsFunction "inv" [Single Port] (Single Port)) [Single 2] (Single 3) ) ] }}} @Display @Heading {Pattern matching} @CNP @ID @Example @Title {Haskell code} { @LP @Haskell { mux2 :: Bit -> (Bit, Bit) -> Bit mux2 Low (a, b) = a mux2 High (a, b) = b}} @CNP @ID @Example @Title {Flat function} { @LP @Haskell { FlatFunction { sigs = [0, 1, 2, 3, 4, 5], args = [Single 0, Tuple [Single 3, Single 4]], res = (Single 5), defs = [ (UncondDef (Lit "'1'") 1), (UncondDef (Eq 0 1) 2), (CondDef 2 4 3 5) ] }}} @End @SubSection @EndSubSections @End @Section @Section @Title {Flattening of functions} @Tag {Flattening} @Begin @LP The most interesting part of all this is of course the translation of our Haskell functions (in Core format) to flattened functions. From there, the translation of VHDL is relatively easy. @LP This section details the "flattening" of a function. To this end, we define a function @I flattenFunction which translates a (nonrecursive) binding to a flat function. @LP The syntax used for these functions is not quite Haskell. It is similar, but some functions can have side effects or don't return any value. They are probably best read as if the lines are sequentially executed (though pattern matching does happen as is normal in Haskell). This notation is probably closest to the monadic "do" notation in Haskell, but with the special syntax for that ("do", "<-" and "return") implied. @LP @Haskell { flattenFunction (NonRec b expr) = (args, res) = flattenExpr expr defs = getDefs FlatFunction args res defs } @LP This is a rather simple function, but it does need some explaination. First of all, the flattenExpr function has some hidden state (In the implementation, this is state is made explicit using a @I State @I Monad). To understand the above function, it is sufficient to know that the @I getDefs function simply returns all the definitions that were added in @I flattenExpr using the @I addDef function. @LP Similary, in the below function definitions, the @I insertBind function inserts a signal bind (that binds a haskell identifier to a signal in the flat function) into the current table of binds. This binds remains in the table for any other functions called by the caller of @I insertBind, but is removed again when that caller "returns". The @I lookupBind function looks up such a bind in this table. @LP Now, the actual work is done by the @I flattenExpr function, which processes an arbitrary expressions and returns a tuple with argument @I SignalMaps and a result @I SignalMap. The argument @I SignalMaps map each argument that should be passed to the expression (when it has a function type, this is an empty list for non-function types). The signals these maps map to are the signals to which the arguments are assumed to have been assigned. In the final @I FlatFunction, these maps are used to tell to which signals the input ports should be bound. @LP The result @I SignalMap is the inverse of the argument @I SIgnalMaps. It contains the signals that the results of the expression are bound to. @Display @Heading {Lambda expressions} @LP @Haskell { flattenExpr (Lam b expr) = arg = genSignals b insertBind (b <= arg) (args, res) = flattenExpr expr (arg:args, res) } @Display @Heading {Variable references} @LP @Haskell { flattenExpr (Var id) = case id of ``localid'' -> ([], lookupBind id) () -> ([], Tuple []) ``datacon'' -> res = genSignals id lit = Lit (dataconToLit id) addDef UncondDef {src = lit, dst = s} ([], res) dataconToLit datacon = case datacon of Low -> "'0'" High -> "'1'" True -> "true" False -> "false" } @LP Here, @I genSignals generates a map of new (unique) signals. The structure on the map is based on the (Haskell) type of whatever is passed to it, such as the value bound to the identifier in this case. @LP The @I ``datacon'' and @I ``localid'' patterns should be read as matching when the id matching against refers to a local identifier (local to the function or expression containing it) or a dataconstructor (such as @I True, @I False, @I High or @I (,)). @Display @Heading {Let expressions} @LP @Haskell { flattenExpr (Let (NonRec b bexpr) expr) = (b_args, b_res) = flattenExpr bexpr insertBind (b <= b_res) flattenExpr expr } @Display @Heading {Case expressions} @LP @Haskell { flattenExpr (Case scrut alts) = (args, res) = flattenExpr scrut flattenAlts res alts flattenAlt scrut alt = TODO flattenAlts scrut [alt] = flattenAlt scrut alt flattenAlts scrut (alt:alts) (true_args, true_res) = flattenAlt scrut alt (false_args, false_res) = flattenAlts scrut alts (altcon, bind_vars, expr) = alt lit = Lit (dataconToLit) TODO } @Display @Heading {Function applications} @LP @Haskell { flattenExpr (App f arg) = TODO } @End @Section # vim: set sts=2 sw=2 expandtab: