f1 >> f2 = f1 >>= \_ -> f2
(>>=) :: Stateful s1 r1 -> (r1 -> Stateful s2 r2) -> Stateful (s1, s2) r2
-f1 >>= f2 = \\(s1, s2) -> let (s1', r1) = f1 s1
+f1 >>= f2 = \(s1, s2) -> let (s1', r1) = f1 s1
(s2', r2) = f2 r1 s2
in ((s1', s2'), r2)
possible, though it will still stay a challenge. Further advances in
dependent typing support for Haskell will probably help here as well.
-TODO: Reference Christiaan and other type-level work
-(http://personal.cis.strath.ac.uk/conor/pub/she/)
+\todo{Reference Christiaan and other type-level work
+(http://personal.cis.strath.ac.uk/conor/pub/she/)}
\item For all recursion, there is the obvious challenge of deciding when
recursion is finished. For list recursion, this might be easier (Since the
base case of the recursion influences the type signatures). For general
to make this set complete, or at least define the constraints on possible
recursion which guarantee it will work.
-TODO: Loop unrolling
+\todo{Reference Christian for loop unrolling?}
\stopitemize
\section{Multiple clock domains and asynchronicity}
func inp _ = inp * 2 + 3
\stophaskell
-TODO: Picture
+\todo{Picture}
In this example, we see that every function takes an input of type
\hs{Event}. The function \hs{main} that takes the output of
because they rely on the the caller to select the clock signal.
This structure is similar to the event handling structure used to perform I/O
-in languages like Amanda. TODO: Ref. There is a top level case expression that
+in languages like Amanda. \todo{ref} There is a top level case expression that
decides what to do depending on the current input event.
A slightly more complex example that shows a system with two clock domains.
particular state variable. This separation is probably a non-trivial problem,
though.
-TODO: Reference "Definitional interpreters for higher-order programming
+\todo{Reference "Definitional interpreters for higher-order programming
languages":
-http://portal.acm.org/citation.cfm?id=805852\&dl=GUIDE\&coll=GUIDE\&CFID=58835435\&CFTOKEN=81856623
+http://portal.acm.org/citation.cfm?id=805852\&dl=GUIDE\&coll=GUIDE\&CFID=58835435\&CFTOKEN=81856623}
\section{New language}
During the development of the prototype, it has become clear that Haskell is
forward would be to define a completely new language with exactly the needed
features. This is of course an enormous effort, which should not be taken
lightly.
+
+\section{Don't care values}
+ A powerful value in \VHDL is the \emph{don't care} value, given as
+ \type{'-'}. This value tells the compiler that you don't really care about
+ which value is assigned to a signal, allowing the compiler to make some
+ optimizations. Since hardware choice in hardware is often implemented using
+ a collection of logic gates instead of multiplexers only, synthesizers can
+ often reduce the amount of hardware needed by smartly choosing values for
+ these don't care cases.
+
+ There is not really anything comparable with don't care values in normal
+ programming languages. The closest thing is an undefined or uninitialized
+ value, though those are usually associated with error conditions.
+
+ It would be useful if Cλash also has some way to specify don't care values.
+ When looking at the Haskell typing system, there are really two ways to do
+ this:
+
+ \startitemize
+ \item Add a special don't care value to every datatype. This includes the
+ obvious \hs{Bit} type, but will also need to include every user defined
+ type. An exception can be made for vectors and product types, since those
+ can simply use the don't care values of the types they contain.
+
+ This would also require some kind of \quote{Dont careable} type class
+ that allows each type to specify what its don't care value is. The
+ compiler must then recognize this constant and replace it with don't care
+ values in the final \VHDL code.
+
+ This is of course a very intrusive solution. Every type must become member
+ of this typeclass, and there is now some member in every type that is a
+ special don't care value. Guaranteeing the obvious don't care semantics
+ also becomes harder, since every pattern match or case statement must now
+ also take care of the don't care value (this might actually be an
+ advantage, since it forces designers to specify how to handle don't care
+ for different operations).
+
+ \item Use the special \hs{undefined}, or \emph{bottom} value present in
+ Haskell. This is a type that is member of all types automatically, without
+ any explicit declarations.
+
+ Any expression that requires evaluation of an undefined value
+ automatically becomes undefined itself (or rather, there is some exception
+ mechanism). Since Haskell is lazy, this means that whenever it tries to
+ evaluate undefined, it is apparently required for determining the output
+ of the system. This property is useful, since typically a don't care
+ output is used when some output is not valid and should not be read. If
+ it is in fact not read, it should never be evaluated and simulation should
+ be fine.
+
+ In practice, this works less ideal. In particular, pattern matching is not
+ always smart enough to deal with undefined. Consider the following
+ definition of an \hs{and} operator:
+
+ \starthaskell
+ or :: Bit -> Bit -> Bit
+ and Low _ = Low
+ and _ Low = Low
+ and High High = High
+ \stophaskell
+
+ When using the \hs{and} operation on an undefined (don't care) and a Low
+ value should always return a Low value. Its value does not depend on the
+ value chosen for the don't care value. However, though when applying the
+ above and function to \hs{Low} and \hs{undefined} results in exactly that
+ behviour, the result is \hs{undefined} when the arguments are swapped.
+ This is because the first pattern forces the first argument to be
+ evaluated. If it is \hs{undefined}, evaluation is halted and an exception
+ is show, which is not what is intended.
+ \stopitemize
+
+ These options should be explored further to see if they provide feasible
+ methods for describing don't care conditions. Possibly there are completely
+ other methods which work better.
projects / matthijs / master-project / report.git / blobdiff