3 @SysInclude { haskell }
4 def @SectionLink right sec {sec @CrossLink {section @NumberOf sec}}
7 @InitialSpace {tex} # Treat multiple spaces as one
8 @Title {From Haskell to VHDL}
9 @Author {Matthijs Kooijman}
10 @Institution {University of Twente}
13 # @OptimizePages {Yes}
18 @LP The aim of this project is to design a structural hardware
19 description language, embedded in the functional language Haskell.
20 This means that a program written in (a subset of) Haskell will be
21 translated into hardware, using a VHDL description. The original
22 Haskell program is a structural description, meaning that the
23 programmer explicitly specifies hardware and area vs time trade-offs
24 are already made explicit in the description and the translator is not
25 required to do any scheduling.
27 @LP The compilation process is divided roughly into four steps:
30 @ParagraphItem { Parsing, typechecking and simplifying the Haskell
31 source(s). By using the API that GHC makes available, this step is
32 fairly easy. We can feed a Haskell source file into GHC, which then
33 performs all the neccesary steps to create a @I Core module, which
34 is a simplified representation of the Haskell source file.}
36 @ParagraphItem { Flattening the function that is the top of the design, and
37 (recursively) any functions it requires. Flattening is the process
38 of removing nesting from expressions in the functions and making the
39 routes values take through an expression more explicit. This results
40 in a flat list of flat functions.}
42 @ParagraphItem { Processing the flattened functions. This step does
43 transformations such as deciding which function arguments will be
44 used as state values, decide names for signals, etc.}
46 @ParagraphItem { Translate the flat functions generated so far into VHDL.
47 This is a fairly direct translation, all information should be
51 @LP In this document we will focus on the second step. The first step
52 is completely handled by GHC and results in a Core module. The
53 representation GHC uses for the Core language is the subject of
54 @SectionLink {Core}. The second step translates
55 a Core module to a set of flat functions. The representation of a flat
56 function is the subject of @SectionLink {FlatFunctions}. The fourth
57 step is also partly discussed in this section. Finally, the actual
58 flattening that happens in the second step is the subject of
59 @SectionLink {Flattening}. The third step remains undiscussed for now.
63 @Title { The Core language }
66 @LP GHC uses an internal representation for Haskell programs called @I
67 {Core} . Core is essentially a small programming language, but we
68 focus on the representation GHC uses. Inside GHC a Core program is
69 stored using a number of custom data types, which we will describe
72 @LP The descriptions given here are therefore very similar to Haskell
73 source, and can usually be interpreted as such. To simplify this
74 discussion, some details that are irrelevant from our point of view
75 are left out, but each of these simplifications is noted in the text.
77 @LP There are two main aspects of Core: Its typing system and its
78 bindings and expression structure.
80 @LP So far, I've focussed on the expression signature without looking closely at
81 the typing structure, except where needed. Thus, I will describe the
82 expression structure a bit here and provide examples to show the relation with
83 Haskell source programs.
87 @Title { Core bindings }
89 @LP A central role in the core language is played by the @I binding. A binding binds
90 one or more expressions to one or more identifiers (@I binders). A core program is
91 essentially a set of bindings, each of which bind to an identifier on global
92 scope (i.e., you get one binding for each function that is defined).
94 The @I CoreBind type is defined as follows:
97 NonRec CoreBndr CoreExpr
98 | Rec [(CoreBndr, CoreExpr)]
101 @LP The @I NonRec constructor is the simplest: It binds a single expression to a
102 single binder. The @I Rec constructors takes a list of binder, expression
103 pairs, and binds each expression to the corresponding binder. These bindings
104 happen on the same scope level, meaning that each expression can use any of
105 the (other) bindings, creating mutually recursive references.
107 @LP When a program is initially compiled to Core, it consists of a single @I Rec
108 binding, containing all the bindings in the original haskell source. These
109 bindings are allowed to reference each other, possibly recursively, but might
110 not. One of the Core simplification passes splits out this large @I Rec
111 constructor into as much small @I Recs and @I NonRecs as possible.
113 @LP The @I CoreBnder type is used in @I Let expressions as well, see below.
117 @Title { Core expressions }
119 @LP The main expression type is @I CoreExpr, @FootNote {In reality, @I CoreExpr
120 is an alias for @I {Expr CoreBndr}, but different types of binders are only
121 used by GHC internally.} which has the following
122 constructors @FootNote{The @I Note constructor was omitted, since it only
123 serves as annotation and does not influence semantics of the expression.}.
127 aformat { @Cell @I A | @Cell B }
131 B {A variable reference}
136 A {App CoreExpr CoreExpr}
137 B {An application. The first expression is the function or data
138 constructor to apply, the second expression is the argument to apply
139 the function to. Function application always applies a single
140 argument, for functions with multiple arguments application is applied
143 A {Lam CoreBndr CoreExpr}
144 B {A lambda expression. When this expression is applied to some argument,
145 the argument is bound to the binder given and the result is the
146 given expression. Or, slightly more formal, the result is the given
147 expression with all @I Var expressions corresponding to the binder
148 replaced with the argument the entire lambda is applied to.}
150 A {Let CoreBind CoreExpr}
152 A let expression. The given bind is one or more binder, expression
153 pairs. Each expression is evaluated and bound to the corresponding
154 binder. The result is of the entire let expression is then the given
157 @DP Or, slightly more formal, evaluates all expressions inside the given bind and
158 returns the given expression with all @I Var expressions corresponding to
159 the binders in the given bind replaced by their respective evaluated
164 Case CoreExpr [CoreAlt]
165 @FootNote {In reality, there are also another Type and CoreBndr
166 arguments. However, the Type argument only contains the type of the
167 entire expression, and thus is redundant and not useful for our purpose.
168 The CoreBndr is a binder to which the scrutinee is bound, but seems
169 this is only used for forcing evaluation of a term. Therefore, these two
170 are left out in this discussion.}
173 A case expression, which can be used to do conditional evaluation and
174 data type ``unpacking''. The given expression (``scrutinee'') is
175 evaluated, bound to the given binder and depending on its value on of
176 the CoreAlts is chosen whose expression is returned.
178 @DP A @I CoreAlt is a three tuple describing the alternative:
180 @IndentedDisplay @I {(AltCon, [CoreBndr], CoreExpr)}
182 @DP Here, the @I AltCon is an alternative constructor which can matched
183 to the scrutinee. An alternative constructor can be one of the default
184 alternative (which matches any value not matched by other alternative
185 constructors in the list), a literal (which matches if the scrutinee
186 evaluates to a literal or a data constructor, which matches if the value
187 is constructed using that specific data constructor.
189 @DP In the last case, when a data constructor is used for the
190 alternative, the arguments to the data constructor are extracted from
191 the scrutinee and bound to the corresponding binders (from the second
192 element of the @I CoreAlt tuple).
194 @DP The last element from the tuple is the expression to return, with
195 the extra bindings in effect.
202 Cast the given expression to the given type. This plays an import role
203 when working with @F newtype declarations and type classes. The exact
204 workings of this expression are a bit shady, but for now we can get away
212 This expression turns a type into an expression, so it can be applied to
213 functions to implement polymorphic functions and type classes. It cannot
214 be used anywhere else.
216 Again, we can can get away with ignore this expression for now.
226 @LP To get a clearer example of how Haskell programs translate to the Core
227 language, a number of programs are given in both Haskell syntax and the
228 equivalent core representation. These are all simple examples, focused on
229 showing a particular aspect of the Core language.
231 @LP In these examples, we will use the following data type. Since most of the
232 primitive datatypes and operators are involved in some kind of
233 polymorphism (Even the + operator is tricky), those are less useful for
234 simple examples. Using the following @I Bit datatype will also make these
235 examples more appropriate for our goals.
238 data Bit = High | Low
241 @Display @Heading {Fixed value}
242 @LP This is a trivial example which shows a simple data constructor without
243 arguments bound to the binders ``high'' and ``low''. Note that in
244 reality, the binder and @I Id values in @I Var nodes include some extra
245 info about the module it is defined in and what kind of identifier it
246 is, but that is left out here for simplicity.
249 @Title {Haskell code}
255 @LP This haskell source results in the following list of @I
259 @Title {Core Structure}
262 [ NonRec ``high'' (Var High)
263 , NonRec ``low'; (Var Low)]}}
265 @LP In subsequent examples I will leave out the @I NonRec constructor and
266 binder name and just show the resulting @I CoreExpr.
268 @Display @Heading {Function arguments}
269 This example shows a simple function that simply returns its argument.
272 @Title {Haskell code}
279 @Title {Core Structure}
284 @Display @Heading { Pattern matching }
285 This example shows a function with a single argument which uses
286 pattern matching, which results in a simple case statement.
289 @Title {Haskell Code}
297 @Title {Core Structure}
303 (High, [], (Var Low)),
304 (Low, [], (Var High))
308 @LP Note that in the tuples describing the alternatives, the first element
309 is a data constructor directly, while the third argument is an expression
310 referring to a dataconstructor (henc the Var constructor).
312 @Display @Heading {Function application}
313 This example shows a function that applies other functions (with one and
314 two arguments) to its own arguments to do its work. It also illustrates
315 functions accepting multiple arguments.
317 @LP For this example we assume there is a function @I nand available to
318 returns the negated and of its two arguments.
321 @Title {Haskell code}
324 or :: Bit -> Bit -> Bit
325 or a b = inv (nand a b)}}
328 @Title {Core structure}
341 @Display @Heading {Tuples}
342 This example shows a function that accepts a tuple of two values and
343 returns a tuple of two values again.
345 @LP This example assumes the availability of two functions @I and and
346 @I xor, with obvious meaning.
349 @Title {Haskell code}
352 -- Accepts two values and returns the sum and carry out respectively.
353 half_adder :: (Bit, Bit) -> (Bit, Bit)
357 @LP Since the core structure corresponding to this (still pretty trivial)
358 function will be quite complex already, we will first show the desugared and
359 simplified version of the function, to which the core structure directly
363 @Title {Simplified haskell code}
369 (,) (and a b) (xor a b)
372 @Title {Core structure}
376 Lam ds (Case (Var ds)
403 @LP Note the (,) in this example, which is the data constructor for a
404 two-tuple. It can be passed two values and will construct a tuple from
405 them. @FootNote {In reality, this dataconstructor takes @I four arguments,
406 namely the types of each of the elements and then the elements themselves.
407 This is because the two-tuple type really takes type arguments, which are
408 made explicit on every call to its data constructors.}
410 @Display @Heading {Let expressions}
411 This example shows a function that uses a let expression to use a value
415 @Title {Haskell code}
418 f :: Bit -> (Bit, Bit)
425 @Title {Simplified haskell code}
433 @Title {Core structure}
463 @Display @Heading {Pattern matching}
464 This example shows a multiplexer, i.e., a function that selects one
465 of two inputs, based on a third input. This illustrates how pattern
466 matching is translated into core and can be used to create
467 conditional signal connections.
470 @Title {Haskell code}
474 mux2 :: Bit -> (Bit, Bit) -> Bit
476 mux2 High (a, b) = b}}
479 @Title {Simplified haskell code}
482 mux2 = \ds ds1 -> case ds of
483 Low -> case ds1 of (a, b) -> a
484 High -> case ds1 of (a, b) -> b}}
487 @Title {Core structure}
491 Lam ds (Lam ds1 (Case (Var ds)
521 @Title {Flat Functions}
524 @LP As an intermediate between Core and VHDL, we use "flat" functions (the name
525 is open for suggestions). A flat function is a simplified version of the
526 function, which defines a number of signals (corresponding to single haskell
527 values) which can be used in a number of places and are defined to a single
528 value. A single value in this case means something that will probably result
529 in a single VHDL signal or port, so a 2-tuple results in two signals, for
532 @LP The function is flat, because there are no directly nested expressions. A
533 function application can only use signals, not nested applications or other
534 expressions. These signals can of course be defined as the result of an
535 expression or function application, so the original expressions can still be
538 @LP A flat function is defined as a single @I FlatFunction constructor with
539 the following fields @FootNote {The implementation additionally has a @I
540 sigs fields listing all the signals, but since that list is directly
541 deducable from the @I args and @I defs fields, it is left out here}:
545 aformat { @Cell @I A | @Cell B }
548 A {args :: [SignalMap]}
549 B {A list that maps each argument to this function to a (number of)
550 signal(s). In other words, this field specifies to which signals the
551 function arguments should be assigned when this function is called.}
554 B {A map that maps the return value to a (number of) signal(s).
555 signal(s). In other words, this field specifies which signals contain
556 the function result when this function is called.}
558 A {defs :: [SignalDef]}
559 B {Definitions for each of the signals in the function. Each @I SignalDef
560 defines one ore more signals, and each signal should be defined exactly
561 once. Note that the signals in @I args don't have a @I SignalDef entry.}
564 @LP The type @I Signal plays a central role in a flat function. It
565 identifies a signal. It's exact representation is not that important (the
566 current implementation uses an Int), as long as it can be compared and
567 unique new @I Signals can be generated.
569 @LP The @I SignalMap type has the following two constructors:
576 @LP This means we can support any type that can be translated to a signal
577 directly (currently only @I Bit and @I Bool) and tuples containing those
578 types. A signal map allows us to decompose a Haskell value into individual
579 pieces that can be used in the resulting VHDL.
581 @LP The @I SignalDef type is slightly more complex. For one or more signals,
582 it specifies how they are defined. In the resulting hardware, these can be
583 mapped to simple signal assignments or port mappings on component
584 instantiations. The type has the following constructors:
587 aformat { @Cell @I A | @Cell B }
592 func :: HsFunction @FootNote {In the current implementation, this
593 value can also be a representation of a higher order function.
594 However, since this is not functional yet, it is left out of this
599 B {A function application. The function that is called is identified by
600 the given @I HsFunction, and passed the values in the given
601 @I SignalMaps as arguments. The result of the function will be
602 assigned to the @I SignalMap in @I res.}
611 B {A conditional signal definition. If the signal pointed to by @I cond
612 is True, @I true is assigned to @I res, else @I false is assigned to
613 @I res. The @I cond signal must thus be of type @I Bool.
615 This keeps conditional assignment very simple, all complexity in the
616 conditions will be put into @I SignalExpr in @I UncondDef. }
622 B {Unconditional signal definition. In the most basic form (assigning a
623 simple signal to another signal) this is not often useful (only in
624 specific cases where two signals cannot be merged, when assigning an
625 output port to an input port for example).
627 The more interesting use for unconditional definition is when the
628 @I SignalExpr is more complicated and allows for more complexity. }
631 @LD @Heading {Identifying functions}
632 @LP To identify a function to call we use the @I HsFunction type. This
633 type is used for two purposes. First, it contains the name of the
634 function to call, so the corresponding @I CoreBndr and @I CoreExpr
635 can be found in the current module. Secondly, an @I HsFunction
636 contains information on the use of each argument and the return
637 value. In particular, it stores for each (part of an) argument or
638 return value if it should become an input or output Port, or a state
639 internal to the called function.
641 @LP The @I HsFunction type looks as follows:
649 @LP Here, the UseMap type is defined similar to the @I SignalMap
650 type @FootNote{In reality, both @I SignalMap and @I UseMap are
651 generalized into a type @I HsValueMap which takes an element type as
658 @LP The @I Use type is defined as follows. The @I StateId argument
659 to the @I State constructor is a unique identifier for the state
660 variable, which can be used to match input and output state
661 variables together. This state id should be unique within either
662 arguments or the return value, but should be matched between them
663 (@I i.e., there should be exactly one @I State use with id 0 in the
664 arguments, and exactly once in the return value) @FootNote{In the
665 current implementation, there is third constructor in the @I Use
666 type for arguments that get higher order functions passed in. Since
667 this is not functional yet, this is left out of this discussion}.
673 @LP The last type used in this description is @I SignalExpr. It allows for certain
674 expressions in the resulting VHDL, currently only comparison. The type has
675 the following constructors:
678 aformat { @Cell @I A | @Cell B }
685 A simple signal reference.
692 A literal value. The given string is the resulting VHDL value. Perhaps
693 this should better be something less VHDL-specific, but this works for
701 Equality comparison. This is the only comparison supported for now and
702 results in a @I Bool signal that can be used in a @I CondDef.
710 @LP To ease the understanding of this datastructure, we will show
711 the flattened equivalents of some of the examples given in
712 @SectionLink {CoreExamples}. When reading these examples, don't
713 forget that the signal id's themselves are interchangeable, as
714 long as they remain unique and still link the right expressions
715 together (@I i.e., the actual numbers are not relevant).
716 @Display @Heading {Fixed value}
719 @Title {Haskell code}
721 @LP @Haskell {high = High}}
723 @LP This Haskell source results in the following @I FlatFunction.
726 @Title {Flat function}
733 defs = [UncondDef (Lit "'1'") 0]
736 @Display @Heading {Function application}
739 @Title {Haskell code}
742 or :: Bit -> Bit -> Bit
743 or a b = inv (nand a b)}}
746 @Title {Flat function}
751 args = [Single 0, Single 1],
755 (HsFunction "nand" [Single Port, Single Port] (Single Port))
760 (HsFunction "inv" [Single Port] (Single Port))
767 @Display @Heading {Pattern matching}
769 @Title {Haskell code}
773 mux2 :: Bit -> (Bit, Bit) -> Bit
775 mux2 High (a, b) = b}}
778 @Title {Flat function}
782 sigs = [0, 1, 2, 3, 4, 5],
783 args = [Single 0, Tuple [Single 3, Single 4]],
786 (UncondDef (Lit "'1'") 1),
787 (UncondDef (Eq 0 1) 2),
797 @Title {Flattening of functions}
800 @LP The most interesting part of all this is of course the translation of our
801 Haskell functions (in Core format) to flattened functions. From there, the
802 translation of VHDL is relatively easy.
804 @LP This section details the "flattening" of a function. To this end, we define
805 a function @I flattenFunction which translates a (nonrecursive) binding to a
808 @LP The syntax used for these functions is not quite Haskell. It is similar,
809 but some functions can have side effects or don't return any value. They
810 are probably best read as if the lines are sequentially executed (though
811 pattern matching does happen as is normal in Haskell). This notation is
812 probably closest to the monadic "do" notation in Haskell, but with the
813 special syntax for that ("do", "<-" and "return") implied.
816 flattenFunction (NonRec b expr) =
817 (args, res) = flattenExpr expr
819 FlatFunction args res defs
822 @LP This is a rather simple function, but it does need some explaination. First
823 of all, the flattenExpr function has some hidden state (In the
824 implementation, this is state is made explicit using a @I State @I Monad).
825 To understand the above function, it is sufficient to know that the @I
826 getDefs function simply returns all the definitions that were added in @I
827 flattenExpr using the @I addDef function.
829 @LP Similary, in the below function definitions, the @I insertBind function
830 inserts a signal bind (that binds a haskell identifier to a signal in the
831 flat function) into the current table of binds. This binds remains in the
832 table for any other functions called by the caller of @I insertBind, but is
833 removed again when that caller "returns". The @I lookupBind function looks
834 up such a bind in this table.
836 @LP Now, the actual work is done by the @I flattenExpr function, which processes
837 an arbitrary expressions and returns a tuple with argument @I SignalMaps and
838 a result @I SignalMap. The argument @I SignalMaps map each argument that
839 should be passed to the expression (when it has a function type, this is an
840 empty list for non-function types). The signals these maps map to are the
841 signals to which the arguments are assumed to have been assigned. In the
842 final @I FlatFunction, these maps are used to tell to which signals the
843 input ports should be bound.
845 @LP The result @I SignalMap is the inverse of the argument @I SIgnalMaps. It
846 contains the signals that the results of the expression are bound to.
848 @Display @Heading {Lambda expressions}
850 flattenExpr (Lam b expr) =
852 insertBind (b <= arg)
853 (args, res) = flattenExpr expr
857 @Display @Heading {Variable references}
859 flattenExpr (Var id) =
867 lit = Lit (dataconToLit id)
868 addDef UncondDef {src = lit, dst = s}
871 dataconToLit datacon =
879 @LP Here, @I genSignals generates a map of new (unique) signals. The structure
880 on the map is based on the (Haskell) type of whatever is passed to it, such
881 as the value bound to the identifier in this case.
883 @LP The @I ``datacon'' and @I ``localid'' patterns should be read as matching
884 when the id matching against refers to a local identifier (local to the
885 function or expression containing it) or a dataconstructor (such as @I True,
886 @I False, @I High or @I (,)).
889 @Display @Heading {Let expressions}
891 flattenExpr (Let (NonRec b bexpr) expr) =
892 (b_args, b_res) = flattenExpr bexpr
893 insertBind (b <= b_res)
897 @Display @Heading {Case expressions}
899 flattenExpr (Case scrut alts) =
900 (args, res) = flattenExpr scrut
903 flattenAlt scrut alt =
906 flattenAlts scrut [alt] =
909 flattenAlts scrut (alt:alts)
910 (true_args, true_res) = flattenAlt scrut alt
911 (false_args, false_res) = flattenAlts scrut alts
912 (altcon, bind_vars, expr) = alt
913 lit = Lit (dataconToLit)
918 @Display @Heading {Function applications}
920 flattenExpr (App f arg) =
927 # vim: set sts=2 sw=2 expandtab: