Explicitely use "letrec" for recursive lets.
[matthijs/master-project/report.git] / FlatFunctions.lout
1 @SysInclude { report }
2 @SysInclude { tbl }
3 @SysInclude { haskell }
4 def @SectionLink right sec {sec @CrossLink {section @NumberOf sec}}
5
6 @Report
7   @InitialSpace {tex} # Treat multiple spaces as one
8   @Title {From Haskell to VHDL}
9   @Author {Matthijs Kooijman}
10   @Institution {University of Twente}
11   @DateLine {Yes}
12   @CoverSheet {No}
13 #  @OptimizePages {Yes}
14 //
15 @Section
16   @Title {Introduction}
17 @Begin
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.
26
27   @LP The compilation process is divided roughly into four steps:
28
29   @LeftList
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.}
35
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.}
41
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.}
45
46     @ParagraphItem { Translate the flat functions generated so far into VHDL.
47     This is a fairly direct translation, all information should be
48     present by now.}
49   @EndList
50
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.
60 @End @Section
61
62 @Section
63   @Title { The Core language }
64   @Tag {Core}
65 @Begin
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
70   here.
71
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.
76
77   @LP There are two main aspects of Core: Its typing system and its
78   bindings and expression structure.
79
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.
84
85 @BeginSubSections
86 @SubSection
87   @Title { Core bindings }
88 @Begin
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).
93
94 The @I CoreBind type is defined as follows:
95
96 @ID @Haskell {
97   NonRec CoreBndr CoreExpr
98   | Rec [(CoreBndr, CoreExpr)]
99 }
100
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.
106
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.
112
113 @LP The @I CoreBnder type is used in @I Let expressions as well, see below.
114 @End @SubSection
115
116 @SubSection
117   @Title { Core expressions }
118 @Begin
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.}.
124
125 @DP
126 @Tbl
127   aformat { @Cell @I A | @Cell B }
128 {
129   @Rowa 
130     A {Var Id} 
131     B {A variable reference}
132   @Rowa
133     A {Lit Literal}
134     B {A literal value}
135   @Rowa
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
141        recursively.}
142   @Rowa
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.}
149   @Rowa
150     A {Let CoreBind CoreExpr}
151     B {
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
155       expression.
156
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
160       expressions.
161     }
162   @Rowa
163     A {
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.}
171     }
172     B {
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.
177       
178       @DP A @I CoreAlt is a three tuple describing the alternative:
179
180       @IndentedDisplay @I {(AltCon, [CoreBndr], CoreExpr)}
181
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.
188
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).
193
194       @DP The last element from the tuple is the expression to return, with
195       the extra bindings in effect.
196     }
197   @Rowa
198     A {
199       Cast CoreExpr Type
200     }
201     B {
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
205       with ignore it.
206     }
207   @Rowa
208     A {
209       Type Type
210     }
211     B {
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.
215
216       Again, we can can get away with ignore this expression for now.
217     }
218 }
219 @DP
220 @BeginSubSubSections
221   @SubSubSection
222     @Title {Examples}
223     @Tag {CoreExamples}
224   @Begin
225
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.
230     
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.
236
237     @ID @Haskell {
238       data Bit = High | Low
239     }
240
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.
247       
248       @CNP @ID @Example
249         @Title {Haskell code}
250       {
251         @LP @Haskell {
252 high = High
253 low = Low}}
254
255       @LP This haskell source results in the following list of @I
256       CoreBndrs.
257        
258       @CNP @ID @Example
259         @Title {Core Structure}
260       {
261       @LP @Haskell {
262 [ NonRec ``high'' (Var High)
263 , NonRec ``low'; (Var Low)]}}
264
265       @LP In subsequent examples I will leave out the @I NonRec constructor and
266       binder name and just show the resulting @I CoreExpr.
267
268     @Display @Heading {Function arguments}
269       This example shows a simple function that simply returns its argument.
270
271       @CNP @ID @Example
272         @Title {Haskell code}
273       {
274         @LP @Haskell {
275 wire :: Bit -> Bit
276 wire a = a}}
277
278       @CNP @ID @Example
279         @Title {Core Structure}
280       {
281         @LP @Haskell {
282 Lam a (Var a)}}
283
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.
287
288     @CNP @ID @Example
289         @Title {Haskell Code}
290       {
291         @LP @Haskell {
292 inv :: Bit -> Bit
293 inv High = Low
294 inv Low = High}}
295
296     @ID @Example
297         @Title {Core Structure}
298       {
299         @LP @Haskell {
300 Lam ds (Case 
301         (Var ds) 
302         [
303                 (High, [], (Var Low)), 
304                 (Low, [], (Var High))
305         ]
306 )}}
307
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).
311
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.
316
317     @LP For this example we assume there is a function @I nand available to
318     returns the negated and of its two arguments.
319
320   @CNP @ID @Example
321     @Title {Haskell code}
322   {
323     @LP @Haskell {
324 or :: Bit -> Bit -> Bit
325 or a b = inv (nand a b)}}
326
327   @CNP @ID @Example
328     @Title {Core structure}
329   {
330     @LP @Haskell {
331 Lam a (Lam b (App
332         (Var inv)
333         (App
334                 (App
335                         (Var nand)
336                         (Var a))
337                 (Var b)
338         )
339 ))}}
340
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.
344
345     @LP This example assumes the availability of two functions @I and and 
346     @I xor, with obvious meaning.
347
348   @CNP @ID @Example
349     @Title {Haskell code}
350   {
351     @LP @Haskell {
352 -- Accepts two values and returns the sum and carry out respectively.
353 half_adder :: (Bit, Bit) -> (Bit, Bit)
354 half_adder (a, b) =
355   (and a b, xor a b)}}
356
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
360   corresponds.
361
362   @CNP @ID @Example
363     @Title {Simplified haskell code}
364   {
365     @LP @Haskell {
366     half_adder = \ds ->
367       Case ds of
368         (a, b) ->
369           (,) (and a b) (xor a b)
370 }}
371   @CNP @ID @Example
372     @Title {Core structure}
373   {
374     @LP @Haskell
375     {
376 Lam ds (Case (Var ds)
377         [(
378                 (,),
379                 [a, b],
380                 (App
381                         (App
382                                 (Var (,))
383                                 (App
384                                         (App
385                                                 (Var and)
386                                                 (Var a)
387                                         )
388                                         (Var b)
389                                 )
390                         )
391                         (App
392                                 (App
393                                         (Var xor)
394                                         (Var a)
395                                 )
396                                 (Var b)
397                         )
398                 )
399         )]
400 )}}
401
402
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.}
409
410   @Display @Heading {Let expressions}
411     This example shows a function that uses a let expression to use a value
412     twice.
413
414   @CNP @ID @Example
415     @Title {Haskell code}
416   {
417     @LP @Haskell {
418 f :: Bit -> (Bit, Bit)
419 f a = 
420   (x, and a x)
421   where
422     x = xor a a}}
423
424   @CNP @ID @Example
425     @Title {Simplified haskell code}
426   {
427     @LP @Haskell {
428     f = \a ->
429       let x = xor a a in
430       (,) x (and a x)
431 }}
432   @CNP @ID @Example
433     @Title {Core structure}
434   {
435     @LP @Haskell
436     {
437 Lam a (Let
438         [(NonRec
439                 x 
440                 (App
441                         (App
442                                 (Var xor)
443                                 (Var a)
444                         )
445                         (Var a)
446                 )
447         )]
448         (App
449                 (App
450                         (Var (,))
451                         (Var x)
452                 )
453                 (App
454                         (App
455                                 (Var and)
456                                 (Var a)
457                         )
458                         (Var x)
459                 )
460         )
461 )}}
462
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.
468
469   @CNP @ID @Example
470     @Title {Haskell code}
471   {
472     @LP @Haskell
473     {
474 mux2 :: Bit -> (Bit, Bit) -> Bit
475 mux2 Low (a, b) = a
476 mux2 High (a, b) = b}}
477
478   @CNP @ID @Example
479     @Title {Simplified haskell code}
480   {
481     @LP @Haskell {
482     mux2 = \ds ds1 -> case ds of
483       Low -> case ds1 of (a, b) -> a
484       High -> case ds1 of (a, b) -> b}}
485
486   @CNP @ID @Example
487     @Title {Core structure}
488   {
489     @LP @Haskell
490     {
491 Lam ds (Lam ds1 (Case (Var ds)
492         [(
493                 Low,
494                 [],
495                 (Case (Var ds1)
496                         [(
497                                 (,)
498                                 [a, b],
499                                 (Var a)
500                         )]
501                 )
502         ),(
503                 High,
504                 [],
505                 (Case (Var ds1)
506                         [(
507                                 (,)
508                                 [a, b],
509                                 (Var b)
510                         )]
511                 )
512         )]
513 ))}}
514   @End @SubSubSection
515 @EndSubSubSections
516 @End @SubSection
517 @EndSubSections
518 @End @Section
519
520 @Section
521   @Title {Flat Functions}
522   @Tag {FlatFunctions}
523 @Begin
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
530   example.
531
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
536   expressed.
537
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}:
542
543   @DP
544   @Tbl
545     aformat { @Cell @I A | @Cell B }
546   {
547     @Rowa 
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.}
552     @Rowa 
553       A {res :: SignalMap}
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.}
557     @Rowa 
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.}
562   }
563
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.
568
569   @LP The @I SignalMap type has the following two constructors:
570   
571   @ID @Haskell {
572 Single Signal
573 | Tuple [SignalMap]
574   }
575   
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.
580
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:
585
586   @DP @Tbl
587     aformat { @Cell @I A | @Cell B }
588   {
589     @Rowa 
590       A {lines @Break {
591 FApp 
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
595     discussion.}
596         args :: [SignalMap]
597         res :: SignalMap
598       }}
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.}
603     @Rowa 
604       A {lines @Break {
605 CondDef 
606         cond :: Signal
607         true :: Signal
608         false :: Signal
609         res :: Signal
610       }}
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.
614
615       This keeps conditional assignment very simple, all complexity in the
616       conditions will be put into @I SignalExpr in @I UncondDef. }
617     @Rowa 
618       A {lines @Break {
619 UncondDef 
620         src :: SignalExpr
621         dst :: Signal}}
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).
626
627       The more interesting use for unconditional definition is when the 
628       @I SignalExpr is more complicated and allows for more complexity. }
629   } 
630
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.
640
641     @LP The @I HsFunction type looks as follows:
642     
643     @ID @Haskell {
644 HsFunction {
645         func :: String,
646         args :: [UseMap],
647         res :: UseMap
648 }}
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
652     a type parameter}:
653
654     @ID @Haskell {
655 Single Use
656 | Tuple [Use]}
657
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}.
668     
669     @ID @Haskell {
670 Port
671 | State StateId}
672
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:
676
677   @DP @Tbl
678     aformat { @Cell @I A | @Cell B }
679   {
680     @Rowa 
681       A {
682         Sig Signal
683       }
684       B {
685         A simple signal reference.
686       }
687     @Rowa
688       A {
689         Literal String
690       }
691       B {
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
694         now.
695       }
696     @Rowa
697       A {
698         Eq Signal Signal
699       }
700       B {
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.
703       }
704   }
705
706   @BeginSubSections
707         @SubSection
708           @Title {Examples}
709         @Begin
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}
717         
718         @CNP @ID @Example
719           @Title {Haskell code}
720         {
721           @LP @Haskell {high = High}}
722       
723         @LP This Haskell source results in the following @I FlatFunction.
724
725         @CNP @ID @Example
726           @Title {Flat function}
727         {
728         @LP @Haskell {
729 FlatFunction {
730         sigs = [0],
731         args = [],
732         res = (Single 0),
733         defs = [UncondDef (Lit "'1'") 0]
734 }}}
735             
736       @Display @Heading {Function application}
737
738         @CNP @ID @Example
739           @Title {Haskell code}
740         {
741           @LP @Haskell {
742 or :: Bit -> Bit -> Bit
743 or a b = inv (nand a b)}}
744
745         @CNP @ID @Example
746           @Title {Flat function}
747         {
748         @LP @Haskell {
749 FlatFunction {
750         sigs = [0, 1, 2, 3],
751         args = [Single 0, Single 1],
752         res = (Single 3),
753         defs = [
754       (FApp   
755         (HsFunction "nand" [Single Port, Single Port] (Single Port))
756         [Single 0, Single 1]
757         (Single 2)
758       ),
759       (FApp
760         (HsFunction "inv" [Single Port] (Single Port))
761         [Single 2]
762         (Single 3)
763       )
764     ]
765 }}}
766
767       @Display @Heading {Pattern matching}
768         @CNP @ID @Example
769           @Title {Haskell code}
770         {
771           @LP @Haskell
772           {
773 mux2 :: Bit -> (Bit, Bit) -> Bit
774 mux2 Low (a, b) = a
775 mux2 High (a, b) = b}}
776
777         @CNP @ID @Example
778           @Title {Flat function}
779         {
780         @LP @Haskell {
781 FlatFunction {
782         sigs = [0, 1, 2, 3, 4, 5],
783         args = [Single 0, Tuple [Single 3, Single 4]],
784         res = (Single 5),
785         defs = [
786                 (UncondDef (Lit "'1'") 1),
787                 (UncondDef (Eq 0 1) 2),
788                 (CondDef 2 4 3 5)
789         ]
790 }}}
791         @End @SubSection
792   @EndSubSections
793
794 @End @Section
795
796 @Section
797   @Title {Flattening of functions}
798   @Tag {Flattening}
799 @Begin
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.
803
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
806   flat function.
807
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.
814
815   @LP @Haskell {
816 flattenFunction (NonRec b expr) =
817         (args, res) = flattenExpr expr
818         defs = getDefs
819         FlatFunction args res defs
820   }
821
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.
828
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.
835
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.
844
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.
847
848   @Display @Heading {Lambda expressions}
849   @LP @Haskell {
850 flattenExpr (Lam b expr) =
851         arg = genSignals b
852         insertBind (b <= arg)
853         (args, res) = flattenExpr expr
854         (arg:args, res)
855   }
856
857   @Display @Heading {Variable references}
858   @LP @Haskell {
859 flattenExpr (Var id) =
860         case id of
861                 ``localid'' -> 
862                         ([], lookupBind id)
863                 () -> 
864                         ([], Tuple [])
865                 ``datacon'' -> 
866                                 res = genSignals id
867                                 lit = Lit (dataconToLit id)
868                                 addDef UncondDef {src = lit, dst = s}
869
870                                 ([], res)
871 dataconToLit datacon =
872         case datacon of
873                 Low -> "'0'"
874                 High -> "'1'"
875                 True -> "true"
876                 False -> "false"
877   }
878
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.
882
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 (,)).
887
888
889   @Display @Heading {Let expressions}
890   @LP @Haskell {
891 flattenExpr (Let (NonRec b bexpr) expr) =
892         (b_args, b_res) = flattenExpr bexpr
893         insertBind (b <= b_res)
894         flattenExpr expr
895   }
896
897   @Display @Heading {Case expressions}
898   @LP @Haskell {
899 flattenExpr (Case scrut alts) =
900         (args, res) = flattenExpr scrut
901         flattenAlts res alts
902
903 flattenAlt scrut alt =
904         TODO
905         
906 flattenAlts scrut [alt] =
907         flattenAlt scrut alt
908
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)
914
915         TODO
916   }
917
918   @Display @Heading {Function applications}
919   @LP @Haskell {
920 flattenExpr (App f arg) =
921         TODO
922   }
923
924
925 @End @Section
926
927 # vim: set sts=2 sw=2 expandtab: