the implementation. The prototype implementation will be discussed in
\in{chapter}[chap:prototype].
- \todo{Shortshort introduction to Cλash (Bit, Word, and, not, etc.)}
-
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
possible.
\placeintermezzo{}{
- \defref{top level binder}
- \defref{top level function}
- \startframedtext[width=8cm,background=box,frame=no]
+ \defref{reading examples}
+ \startframedtext[width=9cm,background=box,frame=no]
\startalignment[center]
- {\tfa Top level binders and functions}
+ {\tfa Reading the examples}
\stopalignment
\blank[medium]
- A top level binder is any binder (variable) that is declared in
- the \quote{global} scope of a Haskell program (as opposed to a
- binder that is bound inside a function.
-
- In Haskell, there is no sharp distinction between a variable and a
- function: a function is just a variable (binder) with a function
- type. This means that a top level function is just any top level
- binder with a function type.
-
- As an example, consider the following Haskell snippet:
-
- \starthaskell
- foo :: Int -> Int
- foo x = inc x
- where
- inc = \y -> y + 1
- \stophaskell
-
- Here, \hs{foo} is a top level binder, whereas \hs{inc} is a
- function (since it is bound to a lambda extraction, indicated by
- the backslash) but is not a top level binder or function. Since
- the type of \hs{foo} is a function type, namely \hs{Int -> Int},
- it is also a top level function.
+ In this thesis, a lot of functional code will be presented. Part of this
+ will be valid Cλash code, but others will just be small Haskell or Core
+ snippets to illustrate a concept.
+
+ In these examples, some functions and types will be used, without
+ properly defining every one of them. These functions (like \hs{and},
+ \hs{not}, \hs{add}, \hs{+}, etc.) and types (like \hs{Bit}, \hs{Word},
+ \hs{Bool}, etc.) are usually pretty self-explanatory.
+
+ The special type \hs{[t]} means \quote{list of \hs{t}'s}, where \hs{t}
+ can be any other type.
+
+ Of particular note is the use of the \hs{::} operator. It is used in
+ Haskell to explicitly declare the type of function or let binding. In
+ these examples and the text, we will occasionally use this operator to
+ show the type of arbitrary expressions, even where this would not
+ normally be valid. Just reading the \hs{::} operator as \quote{and also
+ note that \emph{this} expression has \emph{this} type} should work out.
\stopframedtext
}
+
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
ncline(andb)(out);
\stopuseMPgraphic
- \placeexample[here][ex:And3]{Simple three input and gate.}
+ \placeexample[][ex:And3]{Simple three input and gate.}
\startcombination[2*1]
{\typebufferhs{And3}}{Haskell description using function applications.}
{\boxedgraphic{And3}}{The architecture described by the Haskell description.}
\stopcombination
+ \placeintermezzo{}{
+ \defref{top level binder}
+ \defref{top level function}
+ \startframedtext[width=8cm,background=box,frame=no]
+ \startalignment[center]
+ {\tfa Top level binders and functions}
+ \stopalignment
+ \blank[medium]
+ A top level binder is any binder (variable) that is declared in
+ the \quote{global} scope of a Haskell program (as opposed to a
+ binder that is bound inside a function.
+
+ In Haskell, there is no sharp distinction between a variable and a
+ function: a function is just a variable (binder) with a function
+ type. This means that a top level function is just any top level
+ binder with a function type.
+
+ As an example, consider the following Haskell snippet:
+
+ \starthaskell
+ foo :: Int -> Int
+ foo x = inc x
+ where
+ inc = \y -> y + 1
+ \stophaskell
+
+ Here, \hs{foo} is a top level binder, whereas \hs{inc} is a
+ function (since it is bound to a lambda extraction, indicated by
+ the backslash) but is not a top level binder or function. Since
+ the type of \hs{foo} is a function type, namely \hs{Int -> Int},
+ it is also a top level function.
+ \stopframedtext
+ }
\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
simply be translated to a conditional assignment, where the conditions use
equality comparisons against the constructors in the \hs{case} expressions.
+ In \in{example}[ex:CaseInv] a simple \hs{case} expression is shown,
+ scrutinizing a boolean value. The corresponding architecture has a
+ comparator to determine which of the constructors is on the \hs{in}
+ input. There is a multiplexer to select the output signal. The two options
+ for the output signals are just constants, but these could have been more
+ complex expressions (in which case also both of them would be working in
+ parallel, regardless of which output would be chosen eventually).
+
+ If we would translate a Boolean to a bit value, we could of course remove
+ the comparator and directly feed 'in' into the multiplexer (or even use an
+ inverter instead of a multiplexer). However, we will try to make a
+ general translation, which works for all possible \hs{case} expressions.
+ Optimizations such as these are left for the \VHDL\ synthesizer, which
+ handles them very well.
+
\placeintermezzo{}{
- \defref{substitution notation}
\startframedtext[width=8cm,background=box,frame=no]
\startalignment[center]
{\tfa Arguments / results vs. inputs / outputs}
\stopframedtext
}
- In \in{example}[ex:CaseInv] a simple \hs{case} expression is shown,
- scrutinizing a boolean value. The corresponding architecture has a
- comparator to determine which of the constructors is on the \hs{in}
- input. There is a multiplexer to select the output signal. The two options
- for the output signals are just constants, but these could have been more
- complex expressions (in which case also both of them would be working in
- parallel, regardless of which output would be chosen eventually).
-
- If we would translate a Boolean to a bit value, we could of course remove
- the comparator and directly feed 'in' into the multiplexer (or even use an
- inverter instead of a multiplexer). However, we will try to make a
- general translation, which works for all possible \hs{case} expressions.
- Optimizations such as these are left for the \VHDL\ synthesizer, which
- handles them very well.
+ A slightly more complex (but very powerful) form of choice is pattern
+ matching. A function can be defined in multiple clauses, where each clause
+ specifies a pattern. When the arguments match the pattern, the
+ corresponding clause will be used.
+
+ The architecture described by \in{example}[ex:PatternInv] is of course the
+ same one as the one in \in{example}[ex:CaseInv]. The general interpretation
+ of pattern matching is also similar to that of \hs{case} expressions: generate
+ hardware for each of the clauses (like each of the clauses of a \hs{case}
+ expression) and connect them to the function output through (a number of
+ nested) multiplexers. These multiplexers are driven by comparators and
+ other logic, that check each pattern in turn.
+
+ In these examples we have seen only binary case expressions and pattern
+ matches (\ie, with two alternatives). In practice, case expressions can
+ choose between more than two values, resulting in a number of nested
+ multiplexers.
\startbuffer[CaseInv]
inv :: Bool -> Bool
ncline(mux)(out) "posA(out)";
\stopuseMPgraphic
- \placeexample[here][ex:CaseInv]{Simple inverter.}
+ \placeexample[][ex:CaseInv]{Simple inverter.}
\startcombination[2*1]
{\typebufferhs{CaseInv}}{Haskell description using a Case expression.}
{\boxedgraphic{CaseInv}}{The architecture described by the Haskell description.}
\stopcombination
- A slightly more complex (but very powerful) form of choice is pattern
- matching. A function can be defined in multiple clauses, where each clause
- specifies a pattern. When the arguments match the pattern, the
- corresponding clause will be used.
-
\startbuffer[PatternInv]
inv :: Bool -> Bool
inv True = False
inv False = True
\stopbuffer
- \placeexample[here][ex:PatternInv]{Simple inverter using pattern matching.
+ \placeexample[][ex:PatternInv]{Simple inverter using pattern matching.
Describes the same architecture as \in{example}[ex:CaseInv].}
{\typebufferhs{PatternInv}}
- The architecture described by \in{example}[ex:PatternInv] is of course the
- same one as the one in \in{example}[ex:CaseInv]. The general interpretation
- of pattern matching is also similar to that of \hs{case} expressions: generate
- hardware for each of the clauses (like each of the clauses of a \hs{case}
- expression) and connect them to the function output through (a number of
- nested) multiplexers. These multiplexers are driven by comparators and
- other logic, that check each pattern in turn.
-
- In these examples we have seen only binary case expressions and pattern
- matches (\ie, with two alternatives). In practice, case expressions can
- choose between more than two values, resulting in a number of nested
- multiplexers.
-
\section{Types}
Translation of two most basic functional concepts has been
discussed: function application and choice. Before looking further
ncline(mulb)(out);
\stopuseMPgraphic
- \placeexample[here][ex:Quadruple]{Simple three port and.}
+ \placeexample[][ex:Quadruple]{Simple three port and.}
\startcombination[2*1]
{\typebufferhs{Quadruple}}{Haskell description using function applications.}
{\boxedgraphic{Quadruple}}{The architecture described by the Haskell description.}
\stopuseMPgraphic
- \placeexample[here][ex:DelayAcc]{Simple accumulator architecture.}
+ \placeexample[][ex:DelayAcc]{Simple accumulator architecture.}
\startcombination[2*1]
{\typebufferhs{DelayAcc}}{Haskell description using streams.}
{\boxedgraphic{DelayAcc}}{The architecture described by the Haskell description.}
s' = out
\stopbuffer
- \placeexample[here][ex:ExplicitAcc]{Simple accumulator architecture.}
+ \placeexample[][ex:ExplicitAcc]{Simple accumulator architecture.}
\startcombination[2*1]
{\typebufferhs{ExplicitAcc}}{Haskell description using explicit state arguments.}
% Picture is identical to the one we had just now.
cycle (at best, we could generate hardware that needs an infinite number of
cycles to complete).
+ \placeintermezzo{}{
+ \startframedtext[width=8cm,background=box,frame=no]
+ \startalignment[center]
+ {\tfa \hs{null}, \hs{head} and \hs{tail}}
+ \stopalignment
+ \blank[medium]
+ The functions \hs{null}, \hs{head} and \hs{tail} are common list
+ functions in Haskell. The \hs{null} function simply checks if a list is
+ empty. The \hs{head} function returns the first element of a list. The
+ \hs{tail} function returns containing everything \emph{except} the first
+ element of a list.
+
+ In Cλash, there are vector versions of these functions, which do exactly
+ the same.
+ \stopframedtext
+ }
+
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
projects / matthijs / master-project / report.git / commitdiff