\todo{Shortshort introduction to Cλash (Bit, Word, and, not, etc.)}
- When translating Haskell to hardware, we need to make choices about what kind
- of hardware to generate for which Haskell constructs. When faced with
- choices, we've tried to stick with the most obvious choice wherever
- possible. In a lot of cases, when you look at a hardware description it is
- comletely clear what hardware is described. We want our translator to
- generate exactly that hardware whenever possible, to make working with Cλash
- as intuitive as possible.
+ To translate Haskell to hardware, every Haskell construct needs a
+ translation to \VHDL. There are often multiple valid translations
+ possible. When faced with choices, the most obvious choice has been
+ chosen wherever possible. In a lot of cases, when a programmer looks
+ at a functional hardware description it is completely clear what
+ hardware is described. We want our translator to generate exactly that
+ hardware whenever possible, to make working with Cλash as intuitive as
+ possible.
- In this chapter we try to describe how we interpret a Haskell program from a
+ In this chapter we describe how to interpret a Haskell program from a
hardware perspective. We provide a description of each Haskell language
element that needs translation, to provide a clear picture of what is
supported and how.
\section[sec:description:application]{Function application}
\todo{Sidenote: Inputs vs arguments}
- The basic syntactic element of a functional program are functions and
+ The basic syntactic elements of a functional program are functions and
function application. These have a single obvious \small{VHDL} translation: Each
function becomes a hardware component, where each argument is an input port
and the result value is the (single) output port. This output port can have
{\boxedgraphic{And3}}{The architecture described by the Haskell description.}
\stopcombination
- \note{This section should also mention hierarchy, top level functions and
+ \todo{This section should also mention hierarchy, top level functions and
subcircuits}
\section{Choice}
Although describing components and connections allows us to describe a lot of
hardware designs already, there is an obvious thing missing: Choice. We
need some way to be able to choose between values based on another value.
- In Haskell, choice is achieved by \hs{case} expressions, \hs{if} expressions or
- pattern matching.
+ In Haskell, choice is achieved by \hs{case} expressions, \hs{if}
+ expressions, pattern matching and guards.
An obvious way to add choice to our language without having to recognize
any of Haskell's syntax, would be to add a primivite \quote{\hs{if}}
last one if \hs{B}), all the other ones have no useful value.
An obvious problem with this naive approach is the space usage: The
- example above generates a fairly big \VHDL type. However, we can be
+ example above generates a fairly big \VHDL type. Since we can be
sure that the two \hs{Word}s in the \hs{Sum} type will never be valid
- at the same time, so this is a waste of space.
+ at the same time, this is a waste of space.
Obviously, we could do some duplication detection here to reuse a
particular field for another constructor, but this would only
partially solve the problem. If I would, for example, have an array of
- 8 bits and a 8 bit unsiged word, these are different types and could
+ 8 bits and an 8 bit unsiged word, these are different types and could
not be shared. However, in the final hardware, both of these types
would simply be 8 bit connections, so we have a 100\% size increase by
not sharing these.
In general, we can say we can never properly translate recursive types:
All recursive types have a potentially infinite value (even though in
practice they will have a bounded value, there is no way for the
- compiler to determine an upper bound on its size).
+ compiler to automatically determine an upper bound on its size).
\subsection{Partial application}
Now we've seen how to to translate application, choice and types, we will
calls to the same function share the same machine code. Having more
machine code has implications for speed (due to less efficient caching)
and memory usage. For normal compilation, it is therefore important to
- keep the amount of functions limited and maximize the code sharing.
+ keep the amount of functions limited and maximize the code sharing
+ (though there is a tradeoff between speed and memory usage here).
When generating hardware, this is hardly an issue. Having more \quote{code
sharing} does reduce the amount of \small{VHDL} output (Since different
component instantiations still share the same component), but after
- synthesis, the amount of hardware generated is not affected.
+ synthesis, the amount of hardware generated is not affected. This
+ means there is no tradeoff between speed and memory (or rather,
+ chip area) usage.
In particular, if we would duplicate all functions so that there is a
separate function for every application in the program (\eg, each function
\subsection{Specialization}
\defref{specialization}
- Given some function that has a \emph{domain} $D$ (\eg, the set of all
- possible arguments that could be applied), we create a specialized
- function with exactly the same behaviour, but with a domain $D' \subset
- D$. This subset can be chosen in all sorts of ways. Any subset is valid
- for the general definition of specialization, but in practice only some
- of them provide useful optimization opportunities.
+ Given some function that has a \emph{domain} $D$ (\eg, the set of
+ all possible arguments that the function could be applied to), we
+ create a specialized function with exactly the same behaviour, but
+ with a domain $D' \subset D$. This subset can be chosen in all
+ sorts of ways. Any subset is valid for the general definition of
+ specialization, but in practice only some of them provide useful
+ optimization opportunities.
Common subsets include limiting a polymorphic argument to a single type
(\ie, removing polymorphism) or limiting an argument to just a single
many wires will you lay down for a value that could have any type? When
type classes are involved, what hardware components will you lay down for
a class method (whose behaviour depends on the type of its arguments)?
- Note that the language currently does not allow user-defined typeclasses,
- but does support partly some of the builtin typeclasses (like \hs{Num}).
+ Note that Cλash currently does not allow user-defined typeclasses,
+ but does partly support some of the builtin typeclasses (like \hs{Num}).
Fortunately, we can again use the principle of specialization: Since every
function application generates a separate piece of hardware, we can know
specialized to work just for these specific types, removing the
polymorphism from the applied functions as well.
- Our top level function must not have a polymorphic type (otherwise we
+ \defref{top level function}Our top level function must not have a polymorphic type (otherwise we
wouldn't know the hardware interface to our top level function).
By induction, this means that all functions that are (indirectly) called
\todo{Define pure}
This is a perfect match for a combinatoric circuit, where the output
- also soley depends on the inputs. However, when state is involved, this
+ also solely depends on the inputs. However, when state is involved, this
no longer holds. Since we're in charge of our own language (or at least
let's pretend we aren't using Haskell and we are), we could remove this
purity constraint and allow a function to return different values
the current state is now an argument.
In Haskell, this would look like
- \in{example}[ex:ExplicitAcc]\footnote[notfinalsyntax]{Note that this example is not in the final
+ \in{example}[ex:ExplicitAcc]\footnote[notfinalsyntax]{This example is not in the final
Cλash syntax}. \todo{Referencing notfinalsyntax from Introduction.tex doesn't
work}
\section[sec:recursion]{Recursion}
An import concept in functional languages is recursion. In it's most basic
- form, recursion is a definition that is defined in terms of itself. A
+ form, recursion is a definition that is described in terms of itself. A
recursive function is thus a function that uses itself in its body. This
usually requires multiple evaluations of this function, with changing
arguments, until eventually an evaluation of the function no longer requires
itself.
- Recursion in a hardware description is a bit of a funny thing. Usually,
- recursion is associated with a lot of nondeterminism, stack overflows, but
- also flexibility and expressive power.
-
Given the notion that each function application will translate to a
component instantiation, we are presented with a problem. A recursive
function would translate to a component that contains itself. Or, more
cycle (at best, we could generate hardware that needs an infinite number of
cycles to complete).
- However, most recursive hardware descriptions will describe finite
+ However, most recursive definitions will describe finite
recursion. This is because the recursive call is done conditionally. There
is usually a \hs{case} expression where at least one alternative does not contain
the recursive call, which we call the "base case". If, for each call to the
False -> head xs + sum (tail xs)
\stophaskell
- However, the Haskell typechecker will now use the following reasoning (element
- type of the vector is left out). Below, we write conditions on type
- variables before the \hs{=>} operator. This is not completely valid Haskell
- syntax, but serves to illustrate the typechecker reasoning. Also note that a
- vector can never have a negative length, so \hs{Vector n} implicitly means
- \hs{(n >= 0) => Vector n}.
+ However, the Haskell typechecker will now use the following reasoning.
+ For simplicity, the element type of a vector is left out, all vectors
+ are assumed to have the same element type. Below, we write conditions
+ on type variables before the \hs{=>} operator. This is not completely
+ valid Haskell syntax, but serves to illustrate the typechecker
+ reasoning. Also note that a vector can never have a negative length,
+ so \hs{Vector n} implicitly means \hs{(n >= 0) => Vector n}.
\todo{This typechecker disregards the type signature}
\startitemize
\stopitemize
As you can see, using a simple \hs{case} expression at value level causes
- the type checker to always typecheck both alternatives, which can't be done!
- This is a fundamental problem, that would seem perfectly suited for a type
- class. Considering that we need to switch between to implementations of the
- sum function, based on the type of the argument, this sounds like the
- perfect problem to solve with a type class. However, this approach has its
- own problems (not the least of them that you need to define a new typeclass
- for every recursive function you want to define).
-
- Another approach tried involved using GADTs to be able to do pattern
- matching on empty / non empty lists. While this worked partially, it also
- created problems with more complex expressions.
-
- \note{This should reference Christiaan}
-
- Evaluating all possible (and non-possible) ways to add recursion to our
- descriptions, it seems better to leave out list recursion alltogether. This
- allows us to focus on other interesting areas instead. By including
- (builtin) support for a number of higher order functions like map and fold,
- we can still express most of the things we would use list recursion for.
-
- \todo{Expand on this decision a bit}
-
+ the type checker to always typecheck both alternatives, which can't be
+ done! The typechecker is unable to distinguish the two case
+ alternatives (this is partly possible using \small{GADT}s, but that
+ approach faced other problems \todo{ref christiaan?}).
+
+ This is a fundamental problem, that would seem perfectly suited for a
+ type class. Considering that we need to switch between to
+ implementations of the sum function, based on the type of the
+ argument, this sounds like the perfect problem to solve with a type
+ class. However, this approach has its own problems (not the least of
+ them that you need to define a new typeclass for every recursive
+ function you want to define).
+
+ \todo{This should reference Christiaan}
+
\subsection{General recursion}
Of course there are other forms of recursion, that do not depend on the
length (and thus type) of a list. For example, simple recursion using a
might use some obscure notation that results in a corner case of the
simplifier that is not caught and thus non-termination.
- Due to these complications and limited time available, we leave other forms
- of recursion as future work as well.
+ Evaluating all possible (and non-possible) ways to add recursion to
+ our descriptions, it seems better to limit the scope of this research
+ to exclude recursion. This allows for focusing on other interesting
+ areas instead. By including (builtin) support for a number of higher
+ order functions like \hs{map} and \hs{fold}, we can still express most
+ of the things we would use (list) recursion for.
+
% vim: set sw=2 sts=2 expandtab:
projects / matthijs / master-project / report.git / blobdiff