From: Christiaan Baaij <christiaan.baaij@gmail.com>
Date: Wed, 27 Jan 2010 15:32:56 +0000 (+0100)
Subject: Merge branch 'master' of http://git.stderr.nl/matthijs/projects/cλash-paper
X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=commitdiff_plain;h=38a92f9980362c4e99f1d3143dbc8dbcc84be766

Merge branch 'master' of git.stderr.nl/matthijs/projects/cλash-paper

* 'master' of http://git.stderr.nl/matthijs/projects/cλash-paper:
  Fix typos in related work.
  Make the sumif example fit in a column.
  Improve / shorten the section on types.

Conflicts:
	cλash.lhs
---

38a92f9980362c4e99f1d3143dbc8dbcc84be766
diff --cc "c\316\273ash.lhs"
index ab3c8e2,b646e76..5efc961
--- "a/c\316\273ash.lhs"
+++ "b/c\316\273ash.lhs"
@@@ -558,24 -537,28 +558,24 @@@ mac a b c = add (mul a b) 
      expression, one using only case expressions and one using pattern
      matching and guards.
  
 -\begin{verbatim}
 -sumif cmp a b = if cmp == Eq && a == b 
 -                || cmp == Neq && a != b
 -                then a + b
 -                else 0
 -\end{verbatim}
 -
 -\begin{verbatim}
 -sumif cmp a b = case cmp of
 -  Eq -> case a == b of
 -    True -> a + b
 -    False -> 0
 -  Neq -> case a != b of
 -    True -> a + b
 -    False -> 0
 -\end{verbatim}
 -
 -\begin{verbatim}
 -sumif Eq a b | a == b = a + b
 -sumif Neq a b | a != b = a + b
 -sumif _ _ _ = 0
 -\end{verbatim}
 +\begin{code}
- sumif pred a b = 
-   if    pred == Eq && a == b || pred == Neq && a != b
-   then  a + b
-   else  0
++sumif pred a b = if pred == Eq && a == b 
++                 || pred == Neq && a != b
++                 then  a + b
++                 else  0
 +
 +sumif pred a b = case pred of
 +  Eq ->   case a == b of
 +    True    -> a + b
 +    False   -> 0
 +  Neq ->  case a != b of
 +    True    -> a + b
 +    False   -> 0
 +
 +sumif Eq a b    | a == b = a + b
 +sumif Neq a b   | a != b = a + b
 +sumif _ _ _     = 0
 +\end{code}
  
    TODO: Pretty picture
  
@@@ -731,94 -704,13 +721,52 @@@ data IntPair = IntPair Int In
          These types are translated to \VHDL\ enumerations, with one value for
          each constructor. This allows references to these constructors to be
          translated to the corresponding enumeration value.
-       \item[\textbf{Sum types}]
-         A sum type is an algebraic datatype with multiple constructors, where
-         the constructors have one or more fields. Technically, a type with
-         more than one field per constructor is a sum of products type, but
-         for our purposes this distinction does not really make a
-         difference, so this distinction is note made.
- 
-         The \quote{sum} in its name refers again to the collection of values
-         belonging to this type. The collection for a sum type is the
-         union of the the collections for each of the constructors.
- 
-         Sum types are currently not supported by the prototype, since there is
-         no obvious \VHDL\ alternative. They can easily be emulated, however, as
-         we will see from an example:
- 
- \begin{verbatim}
- data Sum = A Bit Word | B Word
- \end{verbatim}
- 
-         An obvious way to translate this would be to create an enumeration to
-         distinguish the constructors and then create a big record that
-         contains all the fields of all the constructors. This is the same
-         translation that would result from the following enumeration and
-         product type (using a tuple for clarity):
- 
- \begin{verbatim}
- data SumC = A | B
- type Sum = (SumC, Bit, Word, Word)
- \end{verbatim}
- 
-         Here, the \hs{SumC} type effectively signals which of the latter three
-         fields of the \hs{Sum} type are valid (the first two if \hs{A}, the
-         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. Since we can be
-         sure that the two \hs{Word}s in the \hs{Sum} type will never be valid
-         at the same time, this is a waste of space.
- 
-         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
-         example, an array of 8 bits and an 8 bit unsigned 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.
-       \end{xlist}
+       \item[\bf{Multiple constructors with fields}]
+         Algebraic datatypes with multiple constructors, where at least
+         one of these constructors has one or more fields are not
+         currently supported.
 -      \end{xlist}
 -
++    \end{xlist}
  
 +  \subsection{State}
 +    A very important concept in hardware it the concept of state. In a 
 +    stateful design, the outputs depend on the history of the inputs, or the 
 +    state. State is usually stored in registers, which retain their value 
 +    during a clock cycle. As we want to describe more than simple 
 +    combinatorial designs, \CLaSH\ needs an abstraction mechanism for state.
 +
 +    An important property in Haskell, and in most other functional languages, 
 +    is \emph{purity}. A function is said to be \emph{pure} if it satisfies two
 +    conditions:
 +    \begin{inparaenum}
 +      \item given the same arguments twice, it should return the same value in 
 +      both cases, and
 +      \item when the function is called, it should not have observable 
 +      side-effects.
 +    \end{inparaenum}
 +    This purity property is important for functional languages, since it 
 +    enables all kinds of mathematical reasoning that could not be guaranteed 
 +    correct for impure functions. Pure functions are as such a perfect match 
 +    for a combinatorial circuit, where the output solely depends on the 
 +    inputs. When a circuit has state however, it can no longer be simply
 +    described by a pure function. Simply removing the purity property is not a 
 +    valid option, as the language would then lose many of it mathematical 
 +    properties. In an effort to include the concept of state in pure 
 +    functions, the current value of the state is made an argument of the  
 +    function; the updated state becomes part of the result.
 +    
 +    A simple example is the description of an accumulator circuit:
 +    \begin{code}
 +    acc :: Word -> State Word -> (State Word, Word)
 +    acc inp (State s) = (State s', outp)
 +      where
 +        outp  = s + inp
 +        s'    = outp
 +    \end{code}
 +    This approach makes the state of a function very explicit: which variables 
 +    are part of the state is completely determined by the type signature. This 
 +    approach to state is well suited to be used in combination with the 
 +    existing code and language features, such as all the choice constructs, as 
 +    state values are just normal values.
  \section{\CLaSH\ prototype}
  
  foo\par bar