2 \setuppapersize[A4][A4]
4 % Define a custom typescript. We could also have put the \definetypeface's
5 % directly in the script, without a typescript, but I guess this is more
7 \starttypescript[Custom]
8 % This is a sans font that supports greek symbols
9 \definetypeface [Custom] [ss] [sans] [iwona] [default]
10 \definetypeface [Custom] [rm] [serif] [antykwa-torunska] [default]
11 \definetypeface [Custom] [tt] [mono] [modern] [default]
12 \definetypeface [Custom] [mm] [math] [modern] [default]
14 \usetypescript [Custom]
16 % Use our custom typeface
17 \switchtotypeface [Custom] [10pt]
19 % The function application operator, which expands to a space in math mode
21 \define[2]\app{#1\;#2}
22 \define[2]\lam{λ#1 \xrightarrow #2}
23 \define[2]\letexpr{{\bold let}\;#1\;{\bold in}\;#2}
24 \define[2]\case{{\bold case}\;#1\;{\bold of}\;#2}
25 \define[2]\alt{#1 \xrightarrow #2}
26 \define[2]\bind{#1:#2}
27 \define[1]\where{{\bold where}\;#1}
29 \definefloat[transformation][transformations]
31 \startframedtext[width=\textwidth]
36 \define\conclusion{\blackrule[height=0.5pt,depth=0pt,width=.5\textwidth]}
37 \define\nextrule{\vskip1cm}
39 \define[2]\transformold{
40 %\placetransformation[here]{#1}
41 \startframedtext[width=\textwidth]
42 \startformula \startalign
44 \stopalign \stopformula
48 % A shortcut for italicized e.g. and i.e.
49 \define[0]\eg{{\em e.g.}}
50 \define[0]\ie{{\em i.e.}}
54 [location=hanging,hang=20,width=broad]
55 %command=\hskip-1cm,margin=1cm]
57 % Install the lambda calculus pretty-printer, as defined in pret-lam.lua.
58 \installprettytype [LAM] [LAM]
60 \definetyping[lambda][option=LAM,style=sans]
61 \definetype[lam][option=LAM,style=sans]
63 % An (invisible) frame to hold a lambda expression
65 % Put a frame around lambda expressions, so they can have multiple
66 % lines and still appear inline.
67 % The align=right option really does left-alignment, but without the
68 % program will end up on a single line. The strut=no option prevents a
69 % bunch of empty space at the start of the frame.
70 \framed[offset=0mm,location=middle,strut=no,align=right,frame=off]{#1}
74 % Make \typebuffer uses the LAM pretty printer and a sans-serif font
75 % Also prevent any extra spacing above and below caused by the default
76 % before=\blank and after=\blank.
77 \setuptyping[option=LAM,style=sans,before=,after=]
78 % Prevent the arrow from ending up below the first frame (a \framed
79 % at the start of a line defaults to using vmode).
81 % Put the elements in frames, so they can have multiple lines and be
83 \lamframe{\typebuffer[#1]}
84 \lamframe{\Rightarrow}
85 \lamframe{\typebuffer[#2]}
86 % Reset the typing settings to their defaults
87 \setuptyping[option=none,style=\tttf]
89 % This is the same as \transbuf above, but it accepts text directly instead
90 % of through buffers. This only works for single lines, however.
94 \lamframe{\Rightarrow}
99 % A helper to print a single example in the half the page width. The example
100 % text should be in a buffer whose name is given in an argument.
102 % The align=right option really does left-alignment, but without the program
103 % will end up on a single line. The strut=no option prevents a bunch of empty
104 % space at the start of the frame.
106 \framed[offset=1mm,align=right,strut=no]{
107 \setuptyping[option=LAM,style=sans,before=,after=]
109 \setuptyping[option=none,style=\tttf]
114 % A transformation example
115 \definefloat[example][examples]
116 \setupcaption[example][location=top] % Put captions on top
118 \define[3]\transexample{
119 \placeexample[here]{#1}
120 \startcombination[2*1]
121 {\example{#2}}{Original program}
122 {\example{#3}}{Transformed program}
126 \define[3]\transexampleh{
127 % \placeexample[here]{#1}
128 % \startcombination[1*2]
129 % {\example{#2}}{Original program}
130 % {\example{#3}}{Transformed program}
134 % Define a custom description format for the builtinexprs below
135 \definedescription[builtindesc][headstyle=bold,style=normal,location=top]
138 \title {Core transformations for hardware generation}
141 \section{Introduction}
142 As a new approach to translating Core to VHDL, we investigate a number of
143 transforms on our Core program, which should bring the program into a
144 well-defined {\em normal} form, which is subsequently trivial to
147 The transforms as presented here are far from complete, but are meant as
148 an exploration of possible transformations.
151 The transformations described here have a well-defined goal: To bring the
152 program in a well-defined form that is directly translatable to hardware,
153 while fully preserving the semantics of the program.
155 This {\em normal form} is again a Core program, but with a very specific
156 structure. A function in normal form has nested lambda's at the top, which
157 produce a let expression. This let expression binds every function application
158 in the function and produces a simple identifier. Every bound value in
159 the let expression is either a simple function application or a case
160 expression to extract a single element from a tuple returned by a
163 An example of a program in canonical form would be:
166 -- All arguments are an inital lambda
168 -- There is one let expression at the top level
170 -- Calling some other user-defined function.
172 -- Extracting result values from a tuple
173 a = case s of (a, b) -> a
174 b = case s of (a, b) -> b
175 -- Some builtin expressions
178 -- Conditional connections
190 When looking at such a program from a hardware perspective, the top level
191 lambda's define the input ports. The value produced by the let expression is
192 the output port. Most function applications bound by the let expression
193 define a component instantiation, where the input and output ports are mapped
194 to local signals or arguments. Some of the others use a builtin
195 construction (\eg the \lam{case} statement) or call a builtin function
196 (\eg \lam{add} or \lam{sub}). For these, a hardcoded VHDL translation is
199 \subsection{Normal definition}
200 Formally, the normal form is a core program obeying the following
201 constraints. TODO: Update this section, this is probably not completely
202 accurate or relevant anymore.
204 \startitemize[R,inmargin]
205 \item All top level binds must have the form $\expr{\bind{fun}{lamexpr}}$.
206 $fun$ is an identifier that will be bound as a global identifier.
207 \item A $lamexpr$ has the form $\expr{\lam{arg}{lamexpr}}$ or
208 $\expr{letexpr}$. $arg$ is an identifier which will be bound as an $argument$.
209 \item[letexpr] A $letexpr$ has the form $\expr{\letexpr{letbinds}{retexpr}}$.
210 \item $letbinds$ is a list with elements of the form
211 $\expr{\bind{res}{appexpr}}$ or $\expr{\bind{res}{builtinexpr}}$, where $res$ is
212 an identifier that will be bound as local identifier. The type of the bound
213 value must be a $hardware\;type$.
214 \item[builtinexpr] A $builtinexpr$ is an expression that can be mapped to an
215 equivalent VHDL expression. Since there are many supported forms for this,
216 these are defined in a separate table.
217 \item An $appexpr$ has the form $\expr{fun}$ or $\expr{\app{appexpr}{x}}$,
218 where $fun$ is a global identifier and $x$ is a local identifier.
219 \item[retexpr] A $retexpr$ has the form $\expr{x}$ or $\expr{tupexpr}$, where $x$ is a local identifier that is bound as an $argument$ or $result$. A $retexpr$ must
220 be of a $hardware\;type$.
221 \item A $tupexpr$ has the form $\expr{con}$ or $\expr{\app{tupexpr}{x}}$,
222 where $con$ is a tuple constructor ({\em e.g.} $(,)$ or $(,,,)$) and $x$ is
224 \item A $hardware\;type$ is a type that can be directly translated to
225 hardware. This includes the types $Bit$, $SizedWord$, tuples containing
226 elements of $hardware\;type$s, and will include others. This explicitely
227 excludes function types.
230 TODO: Say something about uniqueness of identifiers
232 \subsection{Builtin expressions}
233 A $builtinexpr$, as defined at \in[builtinexpr] can have any of the following forms.
235 \startitemize[m,inmargin]
237 $tuple\_extract=\expr{\case{t}{\alt{\app{con}{x_0\;x_1\;..\;x_n}}{x_i}}}$,
238 where $t$ can be any local identifier, $con$ is a tuple constructor ({\em
239 e.g.} $(,)$ or $(,,,)$), $x_0$ to $x_n$ can be any identifier, and $x_i$ can
240 be any of $x_0$ to $x_n$. A case expression must have a $hardware\;type$.
241 \item TODO: Many more!
244 \section{Transform passes}
246 In this section we describe the actual transforms. Here we're using
247 the core language in a notation that resembles lambda calculus.
249 Each of these transforms is meant to be applied to every (sub)expression
250 in a program, for as long as it applies. Only when none of the
251 expressions can be applied anymore, the program is in normal form. We
252 hope to be able to prove that this form will obey all of the constraints
253 defined above, but this has yet to happen (though it seems likely that
256 Each of the transforms will be described informally first, explaining
257 the need for and goal of the transform. Then, a formal definition is
258 given, using a familiar syntax from the world of logic. Each transform
259 is specified as a number of conditions (above the horizontal line) and a
260 number of conclusions (below the horizontal line). The details of using
261 this notation are still a bit fuzzy, so comments are welcom.
263 TODO: Formally describe the "apply to every (sub)expression" in terms of
264 rules with full transformations in the conditions.
266 \subsection{η-abstraction}
267 This transformation makes sure that all arguments of a function-typed
268 expression are named, by introducing lambda expressions. When combined with
269 β-reduction and function inlining below, all function-typed expressions should
270 be lambda abstractions or global identifiers.
272 \transform{η-abstraction}
276 \lam{E} is not the first argument of an application.
278 \lam{E} is not a lambda abstraction.
280 \lam{x} is a variable that does not occur free in E.
288 foo = λa -> case a of
294 foo = λa.λx -> (case a of
299 \transexample{η-abstraction}{from}{to}
301 \subsection{Extended β-reduction}
302 This transformation is meant to propagate application expressions downwards
303 into expressions as far as possible. In lambda calculus, this reduction
304 is known as β-reduction, but it is of course only defined for
305 applications of lambda abstractions. We extend this reduction to also
306 work for the rest of core (case and let expressions).
320 \transform{Extended β-reduction}
323 \trans{(λx.E) M}{E[M/x]}
327 \trans{(let binds in E) M}{let binds in E M}
339 b = (let y = 3 in add y) 2
348 b = let y = 3 in add y 2
353 \transexample{Extended β-reduction}{from}{to}
355 \subsection{Argument simplification}
356 The transforms in this section deal with simplifying application
357 arguments into normal form. The goal here is to:
360 \item Make all arguments of user-defined functions (\eg, of which
361 we have a function body) simple variable references of a runtime
363 \item Make all arguments of builtin functions either:
365 \item A type argument.
366 \item A dictionary argument.
367 \item A type level expression.
368 \item A variable reference of a runtime representable type.
369 \item A variable reference or partial application of a function type.
373 When looking at the arguments of a user-defined function, we can
374 divide them into two categories:
376 \item Arguments with a runtime representable type (\eg bits or vectors).
378 These arguments can be preserved in the program, since they can
379 be translated to input ports later on. However, since we can
380 only connect signals to input ports, these arguments must be
381 reduced to simple variables (for which signals will be
382 produced). This is taken care of by the argument extraction
384 \item Non-runtime representable typed arguments.
386 These arguments cannot be preserved in the program, since we
387 cannot represent them as input or output ports in the resulting
388 VHDL. To remove them, we create a specialized version of the
389 called function with these arguments filled in. This is done by
390 the argument propagation transform.
393 When looking at the arguments of a builtin function, we can divide them
397 \item Arguments with a runtime representable type.
399 As we have seen with user-defined functions, these arguments can
400 always be reduced to a simple variable reference, by the
401 argument extraction transform. Performing this transform for
402 builtin functions as well, means that the translation of builtin
403 functions can be limited to signal references, instead of
404 needing to support all possible expressions.
406 \item Arguments with a function type.
408 These arguments are functions passed to higher order builtins,
409 like \lam{map} and \lam{foldl}. Since implementing these
410 functions for arbitrary function-typed expressions (\eg, lambda
411 expressions) is rather comlex, we reduce these arguments to
412 (partial applications of) global functions.
414 We can still support arbitrary expressions from the user code,
415 by creating a new global function containing that expression.
416 This way, we can simply replace the argument with a reference to
417 that new function. However, since the expression can contain any
418 number of free variables we also have to include partial
419 applications in our normal form.
421 This category of arguments is handled by the function extraction
423 \item Other unrepresentable arguments.
425 These arguments can take a few different forms:
426 \startdesc{Type arguments}
427 In the core language, type arguments can only take a single
428 form: A type wrapped in the Type constructor. Also, there is
429 nothing that can be done with type expressions, except for
430 applying functions to them, so we can simply leave type
431 arguments as they are.
433 \startdesc{Dictionary arguments}
434 In the core language, dictionary arguments are used to find
435 operations operating on one of the type arguments (mostly for
436 finding class methods). Since we will not actually evaluatie
437 the function body for builtin functions and can generate
438 code for builtin functions by just looking at the type
439 arguments, these arguments can be ignored and left as they
442 \startdesc{Type level arguments}
443 Sometimes, we want to pass a value to a builtin function, but
444 we need to know the value at compile time. Additionally, the
445 value has an impact on the type of the function. This is
446 encoded using type-level values, where the actual value of the
447 argument is not important, but the type encodes some integer,
448 for example. Since the value is not important, the actual form
449 of the expression does not matter either and we can leave
450 these arguments as they are.
452 \startdesc{Other arguments}
453 Technically, there is still a wide array of arguments that can
454 be passed, but does not fall into any of the above categories.
455 However, none of the supported builtin functions requires such
456 an argument. This leaves use with passing unsupported types to
457 a function, such as calling \lam{head} on a list of functions.
459 In these cases, it would be impossible to generate hardware
460 for such a function call anyway, so we can ignore these
463 The only way to generate hardware for builtin functions with
464 arguments like these, is to expand the function call into an
465 equivalent core expression (\eg, expand map into a series of
466 function applications). But for now, we choose to simply not
467 support expressions like these.
470 From the above, we can conclude that we can simply ignore these
471 other unrepresentable arguments and focus on the first two
475 \subsubsection{Argument extraction}
476 This transform deals with arguments to functions that
477 are of a runtime representable type.
479 TODO: It seems we can map an expression to a port, not only a signal.
480 Perhaps this makes this transformation not needed?
481 TODO: Say something about dataconstructors (without arguments, like True
482 or False), which are variable references of a runtime representable
483 type, but do not result in a signal.
485 To reduce a complex expression to a simple variable reference, we create
486 a new let expression around the application, which binds the complex
487 expression to a new variable. The original function is then applied to
490 \transform{Argument extract}
492 \lam{Y} is of a hardware representable type
494 \lam{Y} is not a variable referene
498 \trans{X Y}{let z = Y in X z}
501 \subsubsection{Function extraction}
502 This transform deals with function-typed arguments to builtin functions.
503 Since these arguments cannot be propagated, we choose to extract them
504 into a new global function instead.
506 Any free variables occuring in the extracted arguments will become
507 parameters to the new global function. The original argument is replaced
508 with a reference to the new function, applied to any free variables from
509 the original argument.
511 \transform{Function extraction}
513 \lam{X} is a (partial application of) a builtin function
515 \lam{Y} is not an application
517 \lam{Y} is not a variable reference
521 \lam{f0 ... fm} = free local vars of \lam{Y}
523 \lam{y} is a new global variable
525 \lam{y = λf0 ... fn.Y}
527 \trans{X Y}{X (y f0 ... fn)}
530 \subsubsection{Argument propagation}
531 This transform deals with arguments to user-defined functions that are
532 not representable at runtime. This means these arguments cannot be
533 preserved in the final form and most be {\em propagated}.
535 Propagation means to create a specialized version of the called
536 function, with the propagated argument already filled in. As a simple
537 example, in the following program:
544 we could {\em propagate} the constant argument 1, with the following
552 Special care must be taken when the to-be-propagated expression has any
553 free variables. If this is the case, the original argument should not be
554 removed alltogether, but replaced by all the free variables of the
555 expression. In this way, the original expression can still be evaluated
556 inside the new function. Also, this brings us closer to our goal: All
557 these free variables will be simple variable references.
559 To prevent us from propagating the same argument over and over, a simple
560 local variable reference is not propagated (since is has exactly one
561 free variable, itself, we would only replace that argument with itself).
563 This shows that any free local variables that are not runtime representable
564 cannot be brought into normal form by this transform. We rely on an
565 inlining transformation to replace such a variable with an expression we
568 TODO: Move these definitions somewhere sensible.
570 Definition: A global variable is any variable that is bound at the
571 top level of a program. A local variable is any other variable.
573 Definition: A hardware representable type is a type that we can generate
574 a signal for in hardware. For example, a bit, a vector of bits, a 32 bit
575 unsigned word, etc. Types that are not runtime representable notably
576 include (but are not limited to): Types, dictionaries, functions.
578 Definition: A builtin function is a function for which a builtin
579 hardware translation is available, because its actual definition is not
580 translatable. A user-defined function is any other function.
582 \transform{Argument propagation}
584 \lam{x} is a global variable, bound to a user-defined function
588 \lam{Y_i} is not of a runtime representable type
590 \lam{Y_i} is not a local variable reference
594 \lam{f0 ... fm} = free local vars of \lam{Y_i}
596 \lam{x'} is a new global variable
598 \lam{x' = λy0 ... yi-1 f0 ... fm yi+1 ... yn . E y0 ... yi-1 Yi yi+1 ... yn}
600 \trans{x Y0 ... Yi ... Yn}{x' y0 ... yi-1 f0 ... fm Yi+1 ... Yn}
603 TODO: The above definition looks too complicated... Can we find
604 something more concise?
606 \subsection{Cast propagation}
607 This transform pushes casts down into the expression as far as possible.
608 \subsection{Let recursification}
609 This transform makes all lets recursive.
610 \subsection{Let simplification}
611 This transform makes the result value of all let expressions a simple
613 \subsection{Let flattening}
614 This transform turns two nested lets (\lam{let x = (let ... in ...) in
615 ...}) into a single let.
616 \subsection{Simple let binding removal}
617 This transforms inlines simple let bindings (\eg a = b).
618 \subsection{Function inlining}
619 This transform inlines let bindings of a funtion type. TODO: This should
620 be generelized to anything that is non representable at runtime, or
622 \subsection{Scrutinee simplification}
623 This transform ensures that the scrutinee of a case expression is always
624 a simple variable reference.
625 \subsection{Case binder wildening}
626 This transform replaces all binders of a each case alternative with a
627 wild binder (\ie, one that is never referred to). This will possibly
628 introduce a number of new "selector" case statements, that only select
629 one element from an algebraic datatype and bind it to a variable.
630 \subsection{Case value simplification}
631 This transform simplifies the result value of each case alternative by
632 binding the value in a let expression and replacing the value by a
633 simple variable reference.
634 \subsection{Case removal}
635 This transform removes any case statements with a single alternative and
638 \subsection{Example sequence}
640 This section lists an example expression, with a sequence of transforms
641 applied to it. The exact transforms given here probably don't exactly
642 match the transforms given above anymore, but perhaps this can clarify
643 the big picture a bit.
645 TODO: Update or remove this section.
663 After top-level η-abstraction:
682 After (extended) β-reduction:
700 After return value extraction:
719 Scrutinee simplification does not apply.
721 After case binder wildening:
726 a = case s of (a, _) -> a
727 b = case s of (_, b) -> b
728 r = case s of (_, _) ->
731 Low -> let op' = case b of
740 After case value simplification
745 a = case s of (a, _) -> a
746 b = case s of (_, b) -> b
747 r = case s of (_, _) -> r'
749 rl = let rll = λc.λd.c
762 After let flattening:
767 a = case s of (a, _) -> a
768 b = case s of (_, b) -> b
769 r = case s of (_, _) -> r'
783 After function inlining:
788 a = case s of (a, _) -> a
789 b = case s of (_, b) -> b
790 r = case s of (_, _) -> r'
802 After (extended) β-reduction again:
807 a = case s of (a, _) -> a
808 b = case s of (_, b) -> b
809 r = case s of (_, _) -> r'
821 After case value simplification again:
826 a = case s of (a, _) -> a
827 b = case s of (_, b) -> b
828 r = case s of (_, _) -> r'
846 a = case s of (a, _) -> a
847 b = case s of (_, b) -> b
861 After let bind removal:
866 a = case s of (a, _) -> a
867 b = case s of (_, b) -> b
880 Application simplification is not applicable.