### From Haskell to Hardware

##### June 28, 2015

Conal Elliott uses a reformulated interpretation of lambda calculus to transform Haskell programs into highly parallelized circuits. He gave this talk at Bayhac 2015. His approach allows him to structure parallel programming using a richer set of data structures than the usual array-based thinking. (slides)

### Summary

- We turn Haskell into a tree structure of operations and thence to Verilog
- The same code generates different circuits depending on which types we specify for the polymorphism
- Guiding intuition: overloading lambda and application by using type classes
- The technical steps
- Compile Haskell to the Core language
- Monomorphize
- Convert to abstract vocabulary
- Interpret as circuits
- Synthesize with existing HDL machinery

- It is within the abstract vocabulary that lambdas are overloaded
- The abstract form is not combinatory logic, it is cartesian closed categories
- The idea comes from J. Lambek who showed that there are interpretations of the lambda calculus other than the standard one of functions
- Examples of Haskell programs and the circuits they generate
- Going beyond arrays for parallel programming
- uniform pairs
- vectors of known length
- depth-typed trees, bottom-up and top-down

- Implementing dot products and matrix multiplication
- Generalizing them by relaxing type constraints
- Generates more parallelism, log depth trees rather than linear depth

- Implementing bitonic sort
- Generates fantastically complicated circuits but ones which are certainly correct

- Implementing parallel scan
- Implementing polynomial evaluation in log time
- Combinational circuits have no state, but we can generate stateful ones too
- Using a data type that models a Mealy machine