A library for writing behavioural descriptions in York Lava, inspired by Page and Luk's "Compiling Occam into Field-Programmable Gate Arrays", Oxford Workshop on Field Programmable Logic and Applications, 1991. Features explicit clocking, signals as well as registers, shared procedure calls, and an optimiser. The implementation is short and sweet! Used in the implementation of the Reduceron, a graph reduction machine for Xilinx FPGAs.

To illustrate, consider the implementation of a sequential multiplier using the shift-and-add algorithm.

import Lava import Recipe

We define a state type containing three registers: the two inputs to multiply, and the result of the multiplication.

data Mult n = Mult { a, b, result :: Reg n }

A value of type `Mult n`

is created by `newMult`

.

newMult :: N n => New (Mult n) newMult = return Mult `ap` newReg `ap` newReg `ap` newReg

The shift-and-add recipe operates over a value of type `Mult n`

.

shiftAndAdd s = While (s!b!val =/= 0) $ Seq [ s!a <== s!a!val!shr , s!b <== s!b!val!shl , s!b!val!vhead |> s!result <== s!result!val + s!a!val , Tick ]

shr x = low +> vinit x

shl x = vtail x <+ low

Three remarks are in order:

- The
`!`

operator is flipped application with a high precedence.

infixl 9 ! (!) :: a -> (a -> b) -> b x!f = f x

This gives descriptions an appropriate object-oriented flavour.

- The value of a variable is obtained using the function

val :: Var v => v n -> Word n

Registers (of type `Reg`

) are an instance of the `Var`

class.

- The functions
`+>`

and`<+`

perform cons and snoc operations on vectors,`vhead`

takes the head of a vector, and`=/=`

is generic disequality.

To actually perform a multiplication, the input variables need to be initialised.

multiply x y s = Seq [ s!a <== x, s!b <== y, s!result <== 0, Tick, s!shiftAndAdd ]

example :: Mult N8 -> Recipe example s = s!multiply 5 25

simExample = simRecipe newMult example result

Evaluating `simExample`

yields `25 :: Word N8`

.

See `REDUCERON MEMO 23`

- included in the package and available at
http://www.cs.york.ac.uk/fp/reduceron/ - for further details and
examples.

- data Recipe
- (|>) :: Bit -> Recipe -> Recipe
- call :: Proc -> Recipe
- class Var v where
- (!) :: a -> (a -> b) -> b
- (-->) :: a -> b -> (a, b)
- type New a = RWS Schedule (Bit, Recipe) VarId a
- data Reg n
- newReg :: N n => New (Reg n)
- newRegInit :: N n => Word n -> New (Reg n)
- data Sig n
- newSig :: N n => New (Sig n)
- newSigDef :: N n => Word n -> New (Sig n)
- data Proc
- newProc :: Recipe -> New Proc
- recipe :: New a -> (a -> Recipe) -> Bit -> (a, Bit)
- simRecipe :: Generic b => New a -> (a -> Recipe) -> (a -> b) -> b

# Recipe constructs

Skip | The most basic recipe; does nothing. |

Tick | Does nothing, but takes one clock-cycle to do it. |

Seq [Recipe] | Sequential composition of recipes. |

Par [Recipe] | Fork-Join parallel composition of recipes. |

While Bit Recipe | Run a recipe while a condition holds. |

Do Recipe Bit | Like |

Mutable variables; named locations that can be read from and assigned to.

# The *New* monad

# Mutable variables: registers and signals

*Register variables*: assignments to a register come into effect in
the clock-cycle *after* the assignment is performed; the initial
value of a register is zero unless otherwise specified.

*Signal variables*: assignments to a signal come into effect in the
current clock-cycle, but last only for the duration of that
clock-cycle; if a signal not assigned to in a clock-cycle
then its value will be its *default* value which is zero unless
otherwise specified.

# Shared procedures

newProc :: Recipe -> New ProcSource

Capture a recipe as shared procedure that can be called whenever desired; needless to say, the programmer should avoid parallel calls to the same shared procedure!