expressions, pattern matching and guards.
An obvious way to add choice to our language without having to recognize
expressions, pattern matching and guards.
An obvious way to add choice to our language without having to recognize
function. This function would take three arguments: the condition, the
value to return when the condition is true and the value to return when
the condition is false.
function. This function would take three arguments: the condition, the
value to return when the condition is true and the value to return when
the condition is false.
equality comparisons against the constructors in the \hs{case} expressions.
In \in{example}[ex:Inv] two versions of an inverter are shown. The first
equality comparisons against the constructors in the \hs{case} expressions.
In \in{example}[ex:Inv] two versions of an inverter are shown. The first
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 (which is just a conditional assignment in the generated
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 (which is just a conditional assignment in the generated
\stopdesc
\startdesc{\hs{SizedWord}, \hs{SizedInt}}
These are types to represent integers. A \hs{SizedWord} is unsigned,
\stopdesc
\startdesc{\hs{SizedWord}, \hs{SizedInt}}
These are types to represent integers. A \hs{SizedWord} is unsigned,
has a fixed length. It has two type parameters: its
length and the type of the elements contained in it. By putting the
length parameter in the type, the length of a vector can be determined
has a fixed length. It has two type parameters: its
length and the type of the elements contained in it. By putting the
length parameter in the type, the length of a vector can be determined
The \hs{Vector} type constructor takes two type arguments: the length
of the vector and the type of the elements contained in it. The state
The \hs{Vector} type constructor takes two type arguments: the length
of the vector and the type of the elements contained in it. The state
\stopdesc
\startdesc{\hs{RangedWord}}
This is another type to describe integers, but unlike the previous
\stopdesc
\startdesc{\hs{RangedWord}}
This is another type to describe integers, but unlike the previous
its range is not limited to powers of two, but can be any number.
A \hs{RangedWord} only has an upper bound, its lower bound is
implicitly zero. There is a lot of added implementation complexity
when adding a lower bound and having just an upper bound was enough
its range is not limited to powers of two, but can be any number.
A \hs{RangedWord} only has an upper bound, its lower bound is
implicitly zero. There is a lot of added implementation complexity
when adding a lower bound and having just an upper bound was enough
keyword and type renamings with the \hs{newtype} keyword. \GHC\
offers a few more advanced ways to introduce types (type families,
existential typing, \small{GADT}s, etc.) which are not standard
keyword and type renamings with the \hs{newtype} keyword. \GHC\
offers a few more advanced ways to introduce types (type families,
existential typing, \small{GADT}s, etc.) which are not standard
These types are translated to \VHDL\ record types, with one field for
every field in the constructor. This translation applies to all single
These types are translated to \VHDL\ record types, with one field for
every field in the constructor. This translation applies to all single
field (which are technically not a product, but generate a VHDL
record for implementation simplicity).
\stopdesc
field (which are technically not a product, but generate a VHDL
record for implementation simplicity).
\stopdesc
\defref{enumerated types}
An enumerated type is an algebraic datatype with multiple constructors, but
none of them have fields. This is essentially a way to get an
\defref{enumerated types}
An enumerated type is an algebraic datatype with multiple constructors, but
none of them have fields. This is essentially a way to get an
Note that Haskell's \hs{Bool} type is also defined as an
enumeration type, but we have a fixed translation for that.
Note that Haskell's \hs{Bool} type is also defined as an
enumeration type, but we have a fixed translation for that.
Obviously, duplication detection could be used to reuse a
particular field for another constructor, but this would only
partially solve the problem. If two fields would be, for
Obviously, duplication detection could be used to reuse a
particular field for another constructor, but this would only
partially solve the problem. If two fields would be, for
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.
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{section}[sec:description:application]. It might mean that a
partial application is passed around quite a bit (even beyond function
boundaries), but eventually, the partial application will become
\in{section}[sec:description:application]. It might mean that a
partial application is passed around quite a bit (even beyond function
boundaries), but eventually, the partial application will become
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
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
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. This
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. This
\defref{specialization}
Given some function that has a \emph{domain} $D$ (\eg, the set of
all possible arguments that the function could be applied to), we
\defref{specialization}
Given some function that has a \emph{domain} $D$ (\eg, the set of
all possible arguments that the function could be applied to), we
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
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
When generating hardware, polymorphism cannot be easily translated. How
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
When generating hardware, polymorphism cannot be easily translated. How
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
Note that Cλash currently does not allow user-defined type classes,
but does partly support some of the built-in type classes (like \hs{Num}).
Note that Cλash currently does not allow user-defined type classes,
but does partly support some of the built-in type classes (like \hs{Num}).
stateless (or, \emph{combinational}) design, every output is directly and solely dependent on the
inputs. In a stateful design, the outputs can depend on the history of
inputs, or the \emph{state}. State is usually stored in \emph{registers},
stateless (or, \emph{combinational}) design, every output is directly and solely dependent on the
inputs. In a stateful design, the outputs can depend on the history of
inputs, or the \emph{state}. State is usually stored in \emph{registers},
- which retain their value during a clockcycle, and are typically updated at
- the start of every clockcycle. Since the updating of the state is tightly
+ which retain their value during a clock cycle, and are typically updated at
+ the start of every clock cycle. Since the updating of the state is tightly
Purity is an important property in functional languages, since
it enables all kinds of mathematical reasoning and
Purity is an important property in functional languages, since
it enables all kinds of mathematical reasoning and
\subsubsection{Stream arguments and results}
Including the entire history of each input (\eg, the value of that
\subsubsection{Stream arguments and results}
Including the entire history of each input (\eg, the value of that
depend on all previous input. This is easily done by making every
input a list instead of a single value, containing all previous values
as well as the current value.
depend on all previous input. This is easily done by making every
input a list instead of a single value, containing all previous values
as well as the current value.
ForSyDe, ...} Make functions operate on complete streams. This means
that a function is no longer called on every cycle, but just once. It
takes stream as inputs instead of values, where each stream contains
ForSyDe, ...} Make functions operate on complete streams. This means
that a function is no longer called on every cycle, but just once. It
takes stream as inputs instead of values, where each stream contains
modeled using an (infinite) list, with one element for each clock
cycle. Since the function is only evaluated once, its output must also
be a stream. Note that, since we are working with infinite lists and
modeled using an (infinite) list, with one element for each clock
cycle. Since the function is only evaluated once, its output must also
be a stream. Note that, since we are working with infinite lists and
Since our inputs and outputs are streams, all other (intermediate)
values must be streams. All of our primitive operators (\eg, addition,
Since our inputs and outputs are streams, all other (intermediate)
values must be streams. All of our primitive operators (\eg, addition,
well (note that changing a single-element operation to a stream
operation can done with \hs{map}, \hs{zipwith}, etc.).
This also means that primitive operations from an existing
language such as Haskell cannot be used directly (including some
syntax constructs, like \hs{case} expressions and \hs{if}
well (note that changing a single-element operation to a stream
operation can done with \hs{map}, \hs{zipwith}, etc.).
This also means that primitive operations from an existing
language such as Haskell cannot be used directly (including some
syntax constructs, like \hs{case} expressions and \hs{if}
\small{EDSL}s, since those already impose these same
limitations. \refdef{EDSL}
\small{EDSL}s, since those already impose these same
limitations. \refdef{EDSL}
\subsubsection{Substates}
Since a function's state is reflected directly in its type signature,
\subsubsection{Substates}
Since a function's state is reflected directly in its type signature,
has to somehow know the current state for these called functions. The
only way to do this, is to put these \emph{substates} inside the
caller's state. This means that a function's state is the sum of the
has to somehow know the current state for these called functions. The
only way to do this, is to put these \emph{substates} inside the
caller's state. This means that a function's state is the sum of the
We need some way to know which arguments should become input ports and
which argument(s?) should become the current state (\eg, be bound to
the register outputs). This does not hold just for the top
We need some way to know which arguments should become input ports and
which argument(s?) should become the current state (\eg, be bound to
the register outputs). This does not hold just for the top
- level function, but also for any subfunction. Or could we perhaps
- deduce the statefulness of subfunctions by analyzing the flow of data
+ level function, but also for any sub-function. Or could we perhaps
+ deduce the statefulness of sub-functions by analyzing the flow of data
- To explore this matter, the following observeration is interesting: we
- get completely correct behaviour when we put all state registers in
+ To explore this matter, the following observation is interesting: we
+ get completely correct behavior when we put all state registers in
output ports. Effectively, a stateful function results in a stateless
hardware component that has one of its input ports connected to the
output of a register and one of its output ports connected to the
output ports. Effectively, a stateful function results in a stateless
hardware component that has one of its input ports connected to the
output of a register and one of its output ports connected to the
there will be a lot of extra wire in the design (since registers will
not be close to the component that uses them). Also, when working with
the generated \small{VHDL} code, there will be a lot of extra ports
just to pass on state values, which can get quite confusing.
To fix this, we can simply \quote{push} the registers down into the
there will be a lot of extra wire in the design (since registers will
not be close to the component that uses them). Also, when working with
the generated \small{VHDL} code, there will be a lot of extra ports
just to pass on state values, which can get quite confusing.
To fix this, we can simply \quote{push} the registers down into the
- subcircuits. When we see a register that is connected directly to a
- subcircuit, we remove the corresponding input and output port and put
- the register inside the subcircuit instead. This is slightly less
+ sub-circuits. When we see a register that is connected directly to a
+ sub-circuit, we remove the corresponding input and output port and put
+ the register inside the sub-circuit instead. This is slightly less
trivial when looking at the Haskell code instead of the resulting
circuit, but the idea is still the same.
\todo{Example}
However, when applying this technique, we might push registers down
trivial when looking at the Haskell code instead of the resulting
circuit, but the idea is still the same.
\todo{Example}
However, when applying this technique, we might push registers down
in the caller's state and pass the current value of that state
variable to that same function, the register might get pushed down too
far. It is impossible to distinguish this case from similar code where
in the caller's state and pass the current value of that state
variable to that same function, the register might get pushed down too
far. It is impossible to distinguish this case from similar code where
end up is easier to implement correctly with explicit annotations, so
for these reasons we will look at how this annotations could work.
\todo{Sidenote: one or more state arguments?}
\subsection[sec:description:stateann]{Explicit state annotation}
end up is easier to implement correctly with explicit annotations, so
for these reasons we will look at how this annotations could work.
\todo{Sidenote: one or more state arguments?}
\subsection[sec:description:stateann]{Explicit state annotation}
we need some way for the developer to describe which arguments and
results are intended to become stateful.
we need some way for the developer to describe which arguments and
results are intended to become stateful.
problem for generating hardware.
This is expected for functions that describe infinite recursion. In that
problem for generating hardware.
This is expected for functions that describe infinite recursion. In that
This does imply the extra requirement that the base case is detectable at
compile time. In particular, this means that the decision between the base
This does imply the extra requirement that the base case is detectable at
compile time. In particular, this means that the decision between the base
\subsection{List recursion}
The most common deciding factor in recursion is the length of a list that is
\subsection{List recursion}
The most common deciding factor in recursion is the length of a list that is
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
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
reasoning. Also note that a vector can never have a negative length,
so \hs{Vector n} implicitly means \hs{(n >= 0) => Vector n}.
reasoning. Also note that a vector can never have a negative length,
so \hs{Vector n} implicitly means \hs{(n >= 0) => Vector n}.
\startitemize
\item tail has the type \hs{(n > 0) => Vector n -> Vector (n - 1)}
\item This means that xs must have the type \hs{(n > 0) => Vector n}
\startitemize
\item tail has the type \hs{(n > 0) => Vector n -> Vector (n - 1)}
\item This means that xs must have the type \hs{(n > 0) => Vector n}
- the type checker to always typecheck both alternatives, which cannot be
- done. The typechecker is unable to distinguish the two case
+ the type checker to always type-check both alternatives, which cannot be
+ done. The type-checker 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?}).
alternatives (this is partly possible using \small{GADT}s, but that
approach faced other problems \todo{ref christiaan?}).