Presented by Jeff Palm
Scribed by Peter Douglass
MuFP is an extension of FP a functional programming language. MuFP provides a succinct clear means of describing systolic regular arrays. The purpose of muFP is not to reason about existing circuits, but to derive new circuits.
Combinatorial circuits combine elements by arbitrary arcs. Systolic circuits are distinguished by using latches in all inner arcs. That is, all inner arcs are clocked. Systollic circuits are a significant subclass of meaningful or useful circuits. (Latches are denoted by a dot or circle on the arc.)
A question was raised in the audience whether the clocks for latches in systolic circuit may be driven at different clock rates. The answer is that there is a single global clock. Multiple latches may be used to implement delays representing integral multiples of a clock cycle.
FP maps values to values. MuFP maps streams of values to streams of values. A stream of values is denoted with angled brackets thusly:
<a0, a1, a2,...>
Some primitive functions in muFP are defined.
<<a, b, c> <e, f, g>> => <<a e> <b f> <c g>>
F * G
A law using composition and zip: zip-1 * zip = id
(Discussion of whether zip * zip-1 ? id. This is not well defined.)
is written |_F,G_| and is a function
map F
Discussion: FP originated with Backus. Ethan' talk had the slogan FL = FP + something
A key component of muFP is that the primitive functions have a visual counterpart.
graphics omitted
[| F * G |] = [| F |] * [| G |]
[| [F,G] |] = zip * [ [| F |] , [| G |] ]
[| map F |] = zip * map [| F |] * zip
(graphics omitted)
The tally circuit has output r high if r inputs are high. If given a simple 3 input 1 output tally circuit as a base component, how would one construct a general tally circuit recursively?
(graphics omitted).
Tal(n) = map R * zip * [ apndl * [ 0,Tal(n-1)*mst], [n,n,...,n], apndr * [Tal(n-1)*mst,0]
where
apndl appends an input to the left, apndr appends an input to the right and
mst F <a b c d> = <Fa Fb Fc d>
Note: There is ambiguity in how mst (and many muFP) operators work regarding the number of inputs. mst takes any number of inputs and applies F to all but the last.
This is ugly.
Question: What is Tal(0)? What is the base case? Position put forward that Tal(1) is the identity. Counter position that T(1) has two outputs. Tal(0) has 0 inputs and 1 output which is always high.
FP is a combinator language, with no lambda, let, no lifting of variables, common subexpression elimination
/F
graphics omitted. similar to fold, but with graphic interpretation
R\
graphics omitted
L\
>
R > F applies more and more F's to input. Can anyone think of an circuit that might use the triangle op? Multiplication with shifters.
Plumbing disambiguates the meanings of operators.
Creating a sort circuit from comparison circuits
comp = [smaller, larger]
insert = L \ comp * apl
sort = / ins * last [id]
Q from audience. A stream is infinite. What does it mean to take last of an infinite stream? Streams are _potentially_ infinite.
Q why not take 1st instead of last?
graphics omitted
The goal was to describe systolic circuits, but so far we have only created combinatorial. How to make circuit systolic? The base component in the example is comp. Insert is not systolic. To make it so we use the transformation
sys(Q) => L \ (s D Q)
where D is a latch or D-flip-flop and s is second
we derive
S > D ins = R > D L (S D comp) * appl
eventually we get
= S ins s R > D
so
sort * < > D = systolicSort * m L > D
Punchline: by sprinkling internal latches into non-systolic sort, we have to wait n cycles for output, but get all output lines available at once.
Question. This is combinator programming. What is the relationship to reactive programming? What is relationship to point-free programming? Combinator programming is different from reactive.